二分查找法是一种高效的查找算法，它的思想非常好理解，但编写正确的二分查找并不简单。本章从最基础的二分查找实现开始，讲解其编写技巧，接下来介绍它的四个常见变种的编写，最后应用二分查找来解决真正的面试题，学以致用的同时更加深对其的理解，真正掌握它。
什么是二分查找？
这是一种在有序的数组里快速找到某个元素的高效算法。例如第一章举过的例子：你借了一摞书准备走出书店，其中有一本忘了登记，如何快速找出那本书？你可以一本本的尝试，也可以每一次直接就检测半摞书，再剩下的半摞书依然重复这个过程，这样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，是因为如果l和r都非常大，相加会出现整型溢出的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的终点，
这样的区间可以称j是i的右区间。
对于每一个区间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²)。
最后
本章我们手写实现了二分查找以及它的四个变种，对于如何书写正确的二分查找，也说明了定义边界时的开闭区间问题。还有就是当遇到有序、查找这两个关键词，很容易就能想到使用二分查找法先试试。如果是无序的呢？那就和最后一个题目一样，排序之后再找即可。
作者：huxiaocheng
链接：https://leetcode-cn.com/circle/article/1QJnH6/
网友评论