算法笔记（二）：二分查找

二分查找

1、基础版

public static int binarySearch(int[] a, int target) {int i = 0, j = a.length - 1;while (i <= j) {int m = (i + j) >>> 1;if (target < a[m]) {			// 在左边j = m - 1;} else if (a[m] < target) {		// 在右边i = m + 1;} else {return m;}}return -1;
}

i 是插入点

2、左闭右开区间

核心：j索引位置的元素，一定不是要查找的元素

public static int binarySearch(int[] a, int target) {int i = 0, j = a.length;while (i < j) {int m = (i + j) >>> 1;if (target < a[m]) {			// 在左边j = m;} else if (a[m] < target) {		// 在右边i = m + 1;} else {return m;}}return -1;
}

3、平衡版

问题：当查找的元素在数组最左边或者最右边时，就会导致不平衡

public static int binarySearchBalance(int[] a, int target) {int i = 0, j = a.length;while (1 < j - i) {    //j-i是指还未被比较的元素个数，只有一个时，直接跳出循环int m = (i + j) >>> 1;if (target < a[m]) {j = m;} else {i = m;}}return (a[i] == target) ? i : -1;
}

优点：循环内比较次数少了
缺点：必须等退出循环了才能得到结果

注意：i不能等于m+1，因为else的情况包括target==a[m]，如果i=m+1，那就略过了这个正确的查询结果

4、二分查找 Java 版

private static int binarySearch0(long[] a, int fromIndex, int toIndex,long key) {int low = fromIndex;int high = toIndex - 1;while (low <= high) {int mid = (low + high) >>> 1;long midVal = a[mid];if (midVal < key)low = mid + 1;else if (midVal > key)high = mid - 1;elsereturn mid; // key found}return -(low + 1);  // key not found.
}

例如 $[1, 3, 5, 6]$ 要插入 $2$ ，那么就是找到一个位置，这个位置左侧元素都比它小
- 等循环结束，若没找到，low 左侧元素肯定都比 target 小，因此 low 即插入点
插入点取负是为了与找到情况区分
-1 是为了把索引 0 位置的插入点与找到的情况进行区分

5、最左/最右

对于数组 $[1, 2, 3, 4, 4, 5, 6, 7]$ ，查找元素4，结果是索引3
对于数组 $[1, 2, 4, 4, 4, 5, 6, 7]$ ，查找元素4，结果也是索引3，并不是最左侧的元素

如果希望返回的是要查找的元素中最左侧元素

public static int binarySearchLeftmost1(int[] a, int target) {int i = 0, j = a.length - 1;int candidate = -1;while (i <= j) {int m = (i + j) >>> 1;if (target < a[m]) {j = m - 1;} else if (a[m] < target) {i = m + 1;} else {candidate = m; // 记录候选位置j = m - 1;     // 继续向左}}return candidate;
}

如果希望返回的是要查找的元素中最右侧元素

public static int binarySearchRightmost1(int[] a, int target) {int i = 0, j = a.length - 1;int candidate = -1;while (i <= j) {int m = (i + j) >>> 1;if (target < a[m]) {j = m - 1;} else if (a[m] < target) {i = m + 1;} else {candidate = m; // 记录候选位置i = m + 1;	   // 继续向右}}return candidate;
}

6、最左/最右升级版

对于 Leftmost 与 Rightmost，可以返回一个比 -1 更有用的值

Leftmost 改为

public static int binarySearchLeftmost(int[] a, int target) {int i = 0, j = a.length - 1;while (i <= j) {int m = (i + j) >>> 1;if (target <= a[m]) {j = m - 1;} else {i = m + 1;}}return i; 
}

leftmost 返回值的另一层含义： $\lt target$ 的元素个数
小于等于中间值，都要向左找

Rightmost 改为

public static int binarySearchRightmost(int[] a, int target) {int i = 0, j = a.length - 1;while (i <= j) {int m = (i + j) >>> 1;if (target < a[m]) {j = m - 1;} else {i = m + 1;}}return i - 1;
}