算法通关村第九关——透彻理解二分查找

1.前言

常见的查找算法有顺序查找、二分查找、插值查找、斐波那契查找、树表查找、分块查找、哈希查找等。如果进行归类，那么二分查找、插值查找（一种查找算法）以及斐波那契查找都可以归为插值查找（大类）。而插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。

这些算法中最重要的就是Hash查找和二分查找。

记住：凡是涉及到在排好序的地方（全局或部分）查找的都可以考虑使用二分查找来优化查找效率

插值查找使用的公式为：
$$x=\frac{(key-arr[i])(r-i)}{arr[r]-arr[i]}$$
其中，i和r分别代表数组的第一个和最后一个索引， key代表待查找的元素

分块查找是折半查找和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合解决节点动态变化的情况。

2.基本查找

基本查找也就是顺序查找，不需要在乎数组是否排序，缺点是效率较低。

function search(arr, key) {for (let index = 0; index < arr.length; index++) {if (arr[index] === key) {return index;}}
}

3.二分查找与分治

分治就是把整体拆分为局部，一个复杂的问题可以拆分成很多相似的小问题。二分查找是将中间结果与目标进行比较，一次去掉一半。

3.1 循环方法

// 二分查找——循环方式
function binarySearch(array, low, high, target) {while (low < high) {let mid = (low + high) / 2;if (array[mid] < target) {low = mid + 1；} else if (array[mid] > target) {high = mid - 1;} else {return mid;}}return -1;
}

/ 运算符效率较低,可以写成移位符 >>, 还存在一个问题，当low 和 high 过于大时，low + high可能会溢出，可以将 let mid = (low + high) / 2;改为let mid = low + ((high - low) >> 1);,只要low 和 high 没有溢出，mid就不会溢出。

最终代码如下：

function binarySearch(array, low, high, target) {while (low < high) {let mid = low + ((high - low) >> 1);if (array[mid] < target) {low = mid + 1；} else if (array[mid] > target) {high = mid - 1;} else {return mid;}}return -1;
}

3.2 递归方法

按照递归三步法，代码如下：

// 二分查找——递归方式
function binarySearch(array, low, high, target) {// 递归终止条件if (low <= high) {let mid = low + ((high - low) >> 1);// 不同情况判断if (array[mid] === target) {return mid;} else if (array[mid] < target) {return binarySearch(array, mid + 1, high, target);} else {return binarySearch(array, low, mid - 1, target);}}// 表示没有搜索到return -1;
}

4.有重复元素的二分查找

在上面的基础上，如果元素存在重复，要求如果重复就找左侧第一个，比如[1, 2, 2, 2, 3, 3, 3, 4, 5, 6],要返回第一个2的索引值——1。

分析：基于上面简单的二分查找，在这里我们找到target不要着急返回，而是在重复元素的这个区间继续进行查找，一直找到最左侧的重复元素，再返回最左侧元素的重复索引。在重复元素的这个区间继续进行查找方法有好几种，第一种方法比较简单，就是使用线性查找，一个一个的向左进行查找直到找到最左侧的重复元素。

// 元素中有重复的二分查找，在上面的基础上，元素存在重复，如果重复则找左侧第一个
function binarySearchOfRepeat(array, target) {// 特判if (array === null || array.length  === 0) {return -1;}let left = 0;let right = array.length - 1;while (left <= right) {let mid = left + ((right - left) >> 1);if (array[mid] < target) {left = mid + 1;} else if (array[mid] > target) {right = mid - 1;} else {// 找到目标值后，还应该继续向左侧进行线性查找,直到左侧没有重复值while (mid !== 0 && array[mid] === target) {mid--;}// 如果一直找到了开头还都是重复值，就返回开头if (mid === 0 && array[mid] === target) {return mid;}// 不然就返回mid + 1return mid + 1;}}return -1;
}

这里之所以返回mid + 1,是因为假如序列为[1, 2, 2, 2, 2, 3, 3]，当target=3,当内层的while循环退出时，nums[mid]=2，因此必须返回mid + 1

第二种方法呢就是使用折半查找：

function binarySearchOfRepeat(array, target) {// 特判if (array === null || array.length  === 0) {return -1;}let left = 0;let right = array.length - 1;while (left <= right) {let mid = left + ((right - left) >> 1);if (target < array[mid]) {right = mid - 1;} else if (target > array[mid]) {left = mid + 1;} else {// 如果存在重复元素，在该段重复数组区间内进行折半查找while (left < mid) {				let midLeft = left + ((mid - left) >> 1);// 如果array[midLeft] === target，直接去掉一半右边的重复值if (array[midLeft] === target) {mid = midLeft;} // 如果array[midLeft] !== target，说明超过了重复区间，让left =  midLeft + 1，继续查找else {left =  midLeft + 1;}}return left;}}return -1;
}

拓展——使用递归进行有重复元素的二分查找

再拓展一下，使用递归方法。

function binarySearchOfRepeat(array, target, left, right) {// 不能发生边界逾矩if (left > right) {return -1;}let mid = left + ((right - left) >> 1);if (array[mid] === target) {// 在重复区间内使用递归来找到最左侧的位置let leftmostInRepeat = binarySearchOfRepeat(array, target, left, mid - 1);// 如果没有重复返回mid，如果有重复返回重复区间最左侧值索引return (leftmostInRepeat === -1) ? mid : leftmostInRepeat;} else if (target < array[mid]) {return binarySearchOfRepeat(array, target, left, mid - 1);} else {return binarySearchOfRepeat(array, target, mid + 1, right);}
}function findLeftmostRepeatIndex(array, target) {if (array === null || array.length === 0) {return -1;}return binarySearchOfRepeat(array, target, 0, array.length - 1);
}