前端学数据结构与算法(十一):看似简单又让人抓狂的二分查找算法

835 阅读10分钟

上一篇:前端学数据结构与算法(十):深入理解快速排序

前言

二分查找法是一种高效的查找算法,它的思想非常好理解,但编写正确的二分查找并不简单。本章从最基础的二分查找实现开始,讲解其编写技巧,接下来介绍它的四个常见变种的编写,最后应用二分查找来解决真正的面试题,学以致用的同时更加深对其的理解,真正掌握它。

什么是二分查找?

这是一种在有序的数组里快速找到某个元素的高效算法。例如第一章举过的例子:你借了一摞书准备走出书店,其中有一本忘了登记,如何快速找出那本书?你可以一本本的尝试,也可以每一次直接就检测半摞书,再剩下的半摞书依然重复这个过程,这样12本书,你只用4次即可。像这样每次将数据一分为二的进行查找的算法,就是二分查找法。

二分查找的局限性

虽然说查找的效率很高,跟所有的算法一样,也有其局限性。

1. 必须使用数组

需要借助数组通过下标访问元素只需要O(1)的特性。这一点链表就无法做到,因为访问某个元素必须要遍历,会徒增复杂度。

2. 数据必须是有序的

因为每次是与中间元素进行比较,结果是舍弃一半的查找范围,所以这个中间元素需要起到临界值的作用。

3. 数据量太小没必要使用

数据量太小,和遍历的速度区别不大,那就没必要使用二分查找。也有例外,如果比较操作很耗时,二分查找可以有效减少比较次数,即使数据量小也可以使用二分查找。

基础:二分查找的实现

每次我们拿顺序数组的中间值与需要查找的值进行比对,如果中间值比要查找的值大,就是小区间里查找,反之亦然。思路清楚后,那就上代码,跟着代码更好理解:

function binarySearch(arr, val) {
  let l = 0; // 左侧边界
  let r = arr.length - 1; // 右侧边界
  // 在[l ... r - 1]范围内查找
  
  while (r >= l) { // 终止条件
    const mid = (l + (r - l) / 2) | 0; // 取中间值
    if (arr[mid] === val) { // 正好找到了
      return mid; // 返回对应下标
    } else if (arr[mid] > val) { // 如果当前值大于查找值,去左边界找
      r = mid - 1; // 重新定义右边界,为mid - 1
    } else {
      l = mid + 1; // 重新定义左边界
    }
    
  }
  return -1; // 没找到返回-1
}

const arr = [1, 2, 3, 4, 5, 6, 9, 10];
binarySearch(arr, 10); // 7

这里,也包括之前章节的中间取值都是采用的l + (r - l) / 2 | 0方式,而没采用(r + l) / 2 | 0,是因为如果lr都非常大,相加会出现整型溢出的bug

首先需要得到mid,让数组以它为中心一分为二,左侧是[l ... mid - 1]小区间,右侧是[mid + 1 ... r]大区间。

因为是顺序数组,假如当arr[mid] > val时,就可以直接忽略大区间,要查找的值肯定在小区间里,所以让右侧的边界为r = mid - 1,这里为什么要- 1,因为之前的判断已经表明此时arr[mid]是不等于val的,所以需要将当前元素mid刨除在下次查找的范围内。反之亦然,每次查找都可以忽略一半的范围。直至最终l > r,表示没有找到。

注意开区间与闭区间的区别

为什么二分查找烧脑?根本原因在于它的边界问题,所以开头的时候要定义好边界的含义。

上面版本的二分查找使用的是闭区间定义,右侧边界的定义为r = arr.length - 1,也就是在[l ... r - 1]的范围内进行查找,所以循环的终止条件为r >= l,因为它们相等时数组里还有一个元素没有参与查找。

你也可以采用开区间的定义方式,也就是右侧边界为r === arr.length,在[l ... r )的范围内进行查找。此时循环的截止条件就不能是r >= l了,因为r作为下标存在数组越界的情况,条件需要调整为r > l。而且右侧边界的重新定义就不能是mid - 1了,右边界必须大于要查找元素的下标。开区间二分查找代码如下:

function binarySearch(arr, val) {
  let l = 0;
  let r = arr.length; // 开区间定义
  // 在[l ... r)范围内查找
  
  while (r > l) { // 注意结束条件
    const mid = (l + (r - l) / 2) | 0;
    if (arr[mid] === val) {
      return mid;
    } else if (arr[mid] > val) {
      r = mid; // 重新定义不再 - 1
    } else {
      l = mid + 1;
    }
  }
  return -1;
}

所以书写定义好边界,以及熟悉它的含义,再写出准确无误的二分查找相信也不是难事。

递归版二分查找

其实递归版本的更好理解,因为子过程的重复性是一目了然的,只是性能会比循环略微差一丢丢,不过都是一个复杂度级别,区别很小。代码如下:

function binarySearch(arr, val) {
  const _helper = (arr, l, r) => {
    if (l > r) { // 因为是闭区间,相等时还有元素要比较
      return -1;
    }
    const mid = (l + (r - l) / 2) | 0;
    if (arr[mid] === val) {
      return mid;
    } else if (arr[mid] > val) {
      return _helper(arr, l, mid - 1);
    } else {
      return _helper(arr, mid + 1, r);
    }
  };
  return _helper(arr, 0, arr.length - 1); // 使用闭区间
}

进阶:二分查找的变种

以上的二分查找是建立在数组里没有重复数据的情况下,但假如在一个重复数据的数组里,要返回第一个匹配的元素,上面实现的二分查找就不适应了。这也就是二分查找让人抓狂的变种问题,都需要在基础的二分查找上进行改造以满足需求,常见的有四种变种。

1. 查找第一个匹配的元素

这个查找规则是建立在已经找到了匹配的元素之后,因为是找到第一个,所以首先是判断这个元素是不是数组的第一个元素,然后是已经找到的元素的上一个元素是不匹配的才行。改造的代码如下:

function binarySearch(arr, val) {
  let l = 0;
  let r = arr.length - 1; // 闭区间
  while (r >= l) {
    const mid = (l + (r - l) / 2) | 0;
    if (arr[mid] < val) {
      l = mid + 1;
    } else if (arr[mid] > val) {
      r = mid - 1;
    } else { // 如果已经找到了匹配的元素
      if (mid === 0 || arr[mid - 1] !== val) { 
        // 是数组第一个或前面的元素不匹配,表示找到了
        return mid;
      } else {
        // 否则上一个元素作为右区间继续
        r = mid - 1
      }
    }
  }
  return -1;
}

const arr = [1, 2, 2, 2, 2, 3, 4];
binarySearch(arr, 2) // 1

2. 查找最后一个匹配的元素

跟上一个变种类似,在找到了匹配的元素之后,需要判断这个元素是不是数组的最后一位,还需要判断匹配元素的后一位是不匹配的才行,改造代码如下:

function binarySearch(arr, val) {
  let l = 0;
  let r = arr.length - 1; // 闭区间
  while (r >= l) {
    const mid = (l + (r - l) / 2) | 0;
    if (arr[mid] < val) {
      l = mid + 1;
    } else if (arr[mid] > val) {
      r = mid - 1;
    } else { // 如果已经找到了匹配的元素
      if (mid === arr.length - 1 || arr[mid + 1] !== val) {
        // 是数组最后一个元素或它的后面的不匹配
        return mid;
      } else {
        // 否则下一个元素作为左区间继续
        l = mid + 1
      }
    }
  }
  return -1;
}

const arr = [1, 2, 2, 2, 2, 3, 4];
binarySearch(arr, 2); // 4

3. 查找第一个大于等于匹配的元素

需要在已经找到的大于或等于的位置进行判断,如果这个元素是第一个或它前面的元素是小于要匹配的元素时,说明已经找到了。代码如下:

function binarySearch(arr, val) {
  let l = 0;
  let r = arr.length - 1; // 闭区间
  while (r >= l) {
    const mid = (l + (r - l) / 2) | 0;
    if (arr[mid] >= val) { // 已经找打了大于或等于的元素
      if (mid === 0 || arr[mid - 1] < val) { 
      // 如果是数组的第一个元素或它的前面的元素不匹配 
        return mid;
      } else {
        r = mid - 1; // 缩小右边界
      }
    } else {
      l = mid + 1;
    }
  }
  return -1;
}

const arr = [1, 5, 5, 7, 8, 9];
console.log(binarySearch(arr, 4)); // 1

4. 查找最后一个小于等于匹配的元素

和上一个变种问题类似,重写小于或等于的元素集合即可,代码如下:

function binarySearch(arr, val) {
  let l = 0;
  let r = arr.length - 1; // 闭区间
  while (r >= l) {
    const mid = (l + (r - l) / 2) | 0;
    if (arr[mid] >= val) { // 已经找打了大于或等于的元素
      if (mid === 0 || arr[mid - 1] < val) { 
      // 如果是数组的第一个元素或它的前面的元素不匹配 
        return mid;
      } else {
        r = mid - 1; // 缩小右边界
      }
    } else {
      l = mid + 1;
    }
  }
  return -1;
}

const arr = [1, 2, 2, 7, 8, 9];
console.log(binarySearch(arr, 5)); // 2

实践:求解力扣真题

你以为写出上面几个二分查找法就算掌握了么?真正二分查找的题目细节更讲究,来感受下二分查找为什么让人抓狂吧。

35 - 搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。
如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:
输入: [1, 3, 5, 6], 5
输出: 2

示例 2:
输入: [1, 3, 5, 6], 2
输出: 1

示例 3:
输入: [1, 3, 5, 6], 7
输出: 4

示例 4:
输入: [1, 3, 5, 6], 0
输出: 0

这题的示例已经描述的很清楚了,如果正好右这个元素,就返回这个元素的下标。有序、查找、无重复,这些关键词完全就是为二分查找量身定做,不过有一点和常规的二分查找不同,没有这个元素时返回前一个元素的下标,代码如下:

var searchInsert = function (nums, target) {
  let l = 0;
  let r = nums.length - 1;
  while (r >= l) {
    const mid = (l + (r - l) / 2) | 0;
    if (target > nums[mid]) {
      l = mid + 1;
    } else if (target < nums[mid]) {
      r = mid - 1;
    } else {
      return mid; // 如果等于那就正好
    }
  }
  return l; // 否则返回左侧元素
};

540 - 有序数组中的单一元素

给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。

示例1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2

示例2:
输入: [3,3,7,7,10,11,11]
输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

如果是使用暴力解法,那这道中等的题目就太简单了,最后的注意里面有强调,要保证这个解法在O(logn)级别。题目有交代是有序数组,所以这题很自然会想到使用二分查找法,不过上面写的二分查找好像不适用,麻烦的地方在于怎么确定要查找的元素在哪一边,如何每次抛一半不需要使用的数据。

经过观察,这数组有个特征,长度是奇数,因为只有一个数出现一次,其他数都出现两次。还有就是即使是都是奇数,如果按中间下标均分,它又分为两种情况:

1. 分割后两侧的数组长度为奇数

例如数组长度为7的数组被均分为两个长度3的数组,此时我们要把两个相同的数字作为一个数字处理。这里又分为两种情况:

1.1 - 中间元素与前一个相同,此时唯一不同的那个元素必然是在右侧,左侧是可以忽略的,而且下一次开始的下标从mid + 1开始即可。

1.2 - 中间元素与后一个相同,唯一不同的那个元素必然是在左侧,右侧可以忽略,且下一次截止的位置为mid - 1

2. 分割后两侧的数组长度为偶数

此时还是分为两种情况来处理,与之前分割为奇数的恰恰相反:

2.1 - 中间元素与前一个元素相同时,唯一不同的那个元素在左侧部分,因为既然都是偶数,哪边有相同的元素,哪边就是奇数数组了,下一次查找截止的位置为mid - 2

2.2 - 同理,中间元素与后一个元素相同,唯一不同的元素就在右侧,而且下一次开始的位置为mid + 2

知道了怎么均分数组,也知道了边界怎么重定义,这个解法就很容易写出来了。不过还有一个注意点就是,当数组里只能一个元素的时候就不用比较了,必定是那个元素。完整代码如下:

var singleNonDuplicate = function (nums) {
  let l = 0;
  let r = nums.length - 1;
  while (r > l) { // 闭区间保留最后一个元素
    const mid = (l + (r - l) / 2) | 0;
    const splitIntoEven = (mid - l) % 2 === 0; // 分割后是否是偶数长度
    if (nums[mid] === nums[mid + 1]) { // 如果与前一个相同
      if (splitIntoEven) { // 而且左右是偶数长度
        l = mid + 2; // 符合2.2的情况
      } else {
        r = mid - 1; // 符合1.2
      }
    } else if (nums[mid] === nums[mid - 1]) { // 与后一个相同
      if (splitIntoEven) { // 是偶数长度
        r = mid - 2; // 符合2.1
      } else {
        l = mid + 1; // 符合1.1
      }
    } else {
      return nums[mid]; // 当前元素和前后都不相同,返回这个异类
    }
  }
  return nums[l]; // 返回最后一个元素
};

436 - 寻找右区间

有一个二维数组,里面每一个单独的数组i都表示的是一个区间值,第一个元素是该区间的起始点,
第二个元素是该区间终点。问是否有另一个区间j,它的起始点大于或等于区间i的终点,
这样的区间可以称ji的右区间。

对于每一个区间i,你需找到它的下标值最小右区间,如果没有则返回-1。

注意:
你可以假设区间的终点总是大于它的起始点。
你可以假定这些区间都不具有相同的起始点。

示例 1:
输入: [ [3,4], [2,3], [1,2] ]
输出: [-1, 0, 1]

解释:
对于[3,4],没有满足条件的“右侧”区间。
对于[2,3],区间[3,4]具有最小的“右”起点;
对于[1,2],区间[2,3]具有最小的“右”起点。

对于每一个区间i,需要找到另外一个区间j,这个j的起始点要大于等于i的终点。但是这样的区间可能会有多个,我们需要找到符合这个要求且下标值最小的那一项。

我们使用排序即可,按照起始点从升序排列,依次遍历时,符合条件的第一项,绝对就是下标值最小的那一项。但此时会遇到另外一个问题,就是排序之后的下标和最初的下标不同,此时我们可以使用map记录下最初的下标值。找到符合的区间后,查看该区间最初的下标,添加到返回的集合里即可。代码如下:

var findRightInterval = function (intervals) {
  const res = []; // 最终返回的结果
  const map = new Map(); // 记录最初的下标
  for (let i = 0; i < intervals.length; i++) {
    map.set(intervals[i], i); // 使用区间作为key
  }
  intervals.sort((a, b) => a[0] - b[0]); // 按照起始点升序排列

  for (let i = 0; i < intervals.length; i++) {
    let minIndex = -1;
    let l = i;
    let r = intervals.length - 1;
    while (r >= l) { // 闭区间,最后一个元素也要比较
      const mid = (l + (r - l) / 2) | 0;
      if (intervals[mid][0] >= intervals[i][1]) { // 如果符合
        minIndex = map.get(intervals[mid]); // 取得原始下标
        r = mid - 1 // 换小的起始点继续
      } else {
        l = mid + 1 // 不符合换大的起始点继续
      }
    }
    res[map.get(intervals[i])] = minIndex; 
    // intervals[i]是排序后所在的位置
    // 而map.get(intervals[i])找到的又是它原始的下标位置
    // minIndex对应的是其原始项的最小右区间
  }
  return res; // 返回集合
};

因为二分查找只能作用于有序的数组,所以数组无序时,我们可以先对其进行排序。如果不使用二分查找,第二层循环依然遍历,整体的复杂度就会变为O(n²)

最后

本章我们手写实现了二分查找以及它的四个变种,对于如何书写正确的二分查找,也说明了定义边界时的开闭区间问题。还有就是当遇到有序、查找这两个关键词,很容易就能想到使用二分查找法先试试。如果是无序的呢?那就和最后一个题目一样,排序之后再找即可。

上一篇:前端学数据结构与算法(十二):有趣的算法 - 多指针与滑动窗口