二分查找

DogJay 2019-05-07 后端技术 803人已围观

1. 正常实现

public int binarySearch(int[] nums, int key) {
    int l = 0, h = nums.length - 1;
    while (l <= h) {
        int m = l + (h - l) / 2;
        if (nums[m] == key) {
            return m;
        } else if (nums[m] > key) {
            h = m - 1;
        } else {
            l = m + 1;
        }
    }
    return -1;
}

2. 时间复杂度

二分查找也称为折半查找,每次都能将查找区间减半,这种折半特性的算法时间复杂度为 O(logN)。

3. m 计算

有两种计算中值 m 的方式:

  • m = (l + h) / 2
  • m = l + (h - l) / 2

l + h 可能出现加法溢出,最好使用第二种方式。

4. 返回值

循环退出时如果仍然没有查找到 key,那么表示查找失败。可以有两种返回值:

  • -1:以一个错误码表示没有查找到 key
  • l:将 key 插入到 nums 中的正确位置

5. 变种

二分查找可以有很多变种,变种实现要注意边界值的判断。例如在一个有重复元素的数组中查找 key 的最左位置的实现如下:

public int binarySearch(int[] nums, int key) {
    int l = 0, h = nums.length - 1;
    while (l < h) {
        int m = l +