代码之神 2019-06-27
二分查找法的思想非常简单,对于一个有序数列,找它中间的元素,看是否是查找目标,如果不是,就看这个查找目标是小于还是大于中间元素,然后在对应的区间内重复上述过程。
需要注意几个问题:
while 循环:while 循环的条件应该是 left < right 还是 left <= right 呢?
target 和 arr[mid] 的判断:当 target > arr[mid] 时,是应该 left = mid 还是 left = mid + 1 呢?
private int binarySearch(T arr[], int n, T target) { int left = 0, right = n - 1; // 在 [left, right] 区间内寻找 target while (left <= right) { // 当 left = right 时,区间 [left, right] 仍然有效 int mid = (left + right) / 2; if (arr[mid] == target) return mid; if (target > arr[mid]) left = mid + 1; // target 在 [mid+1, r] 中 else right = mid - 1; // target 在 [left, mid - 1] 中 } return -1; }
不知道到这里大家有没有发现一个 bug
因为 left 和 right 都是 int,所以当值足够大时,在计算 mid = (left + right) / 2 时可能会发生整型溢出!
因此,为了避免这个问题,我们使用减法来计算。
完全正确的二分查找法
public int binarySearch(T[] arr, int n, T target) { int left = 0, right = n - 1; // 在 [left, right] 区间内寻找 target while (left <= right) { // 当 left = right 时,区间 [left, right] 仍然有效 int mid = left + (right - left) / 2; if (arr[mid].compareTo(target) == 0) return mid; if (target.compareTo(arr[mid]) > 0) left = mid + 1; // target 在 [mid+1, r] 中 else right = mid - 1; // target 在 [left, mid - 1] 中 } return -1; }
我们可以写一个 Util 来帮助我们生成测试用例
ArrayUtil.java
public static Integer[] generateSortedArray(int n) { assert n > 0; Integer[] arr = new Integer[n]; for (int i = 0; i < n; i++) { arr[i] = i; } return arr; }
BinarySearch.java
public static void main(String[] args) { BinarySearch<Integer> bs = new BinarySearch<Integer>(); int n = (int)Math.pow(10, 7); // 用 10,000,000 数据测试 Integer[] data = ArrayUtil.generateSortedArray(n); long startTime = System.currentTimeMillis(); for (int i = 0; i < n; i++) if (i != bs.binarySearch(data, n, i)) throw new IllegalStateException("find i failed"); long endTime = System.currentTimeMillis(); System.out.println("Binary Search success!"); System.out.println("Time cost: " + (endTime - startTime) + "ms"); }