mahaaoo
0%

二分查找

Posted on In

简介

二分查找（Binary Search）算法，也叫折半查找算法。在给顺序表结构中（也就是数组）快速查找某一个值或者某个区间。二分查找的时间复杂度是O(logn)。虽然二分查找看起来很简单，实现出来的代码不够寥寥十几行，但是就是会出错，要么漏个等号，要么少加1。也就是思路很简单，细节是魔鬼

本文均抄自Leetcode精选解题，本文原作者是labuladong

模版

二分查找的写法基本固定，根据不同的场景修改起始值、判断条件、中止值非常容易忽略细节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function binarySearch(nums, target) {
    let left = 0, 
    let right = ...;

    while(...) {
        let mid = parseInt((right + left) / 2); // 向下取整
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

关于mid的取值问题，mid=（right+left）/2是有问题的，因为当right和left比较大的时候，相加的值有可能导致溢出。改进的方法是写成mid = left + (right-left)/2。如果要进行极致的性能优化，可以将除以2的操作写成位运算，left + (right-left) >> 1，相比于除法，计算机计算位运算的速度更快。

本文均写成(right + left) / 2方便阅读，给定的数组均是升序数组

查找某一固定值

在给定的升序数组中，查找该数组中的某一个值，返回该值在数组中所处下标位置，若不存在该值则返回-1

例：给定数组[1,3,4,6,9,11,23,55]，查找数字6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length-1;

    while(left<=right) {
        let mid = parseInt((right + left) / 2);
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1;
}

  • 为什么 while 循环的条件中是 <=，而不是 < ？

    因为right初始化的值是nums.length-1，即数组中最后一个元素，而不是nums.length。

    这二者可能出现在不同功能的二分查找中，区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引大小为 nums.length 是越界的。

    我们这个算法中使用的是前者 [left, right] 两端都闭的区间。这个区间其实就是每次进行搜索的区间，我们不妨称为「搜索区间」。

    什么时候应该停止搜索呢？当然，找到了目标值的时候可以终止：

    1
    2
    3
    if (nums[mid] == target) {
       return mid;
    }

    但如果没找到，就需要 while 循环终止，然后返回 -1。那 while 循环什么时候应该终止？搜索区间为空的时候应该终止，意味着你没得找了，就等于没找到嘛。

    while(left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候搜索区间为空，因为没有数字既大于等于 33 又小于等于 22 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

    while(left < right) 的终止条件是 left == right，写成区间的形式就是 [left, right]，或者带个具体的数字进去 [2, 2]，这时候搜索区间非空，还有一个数 22，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 22 没有被搜索，如果这时候直接返回 -1 就是错误的。

  • 为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？

    这也是二分查找的一个难点，不过只要你能理解前面的内容，就能够很容易判断。

    刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，如何确定下一步的搜索区间呢？

    当然是 [left, mid - 1] 或者 [mid + 1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。

查找第一个等于给定元素的值(左边界)

类似于上一个例子，现在我们给定的数组变成了[1,6,6,6,9]，需要返回第一个等于6的元素的下标。运行上面的函数返回值为2，因为第一个值的mid就等于了6。那么如何改进二分查找，才能找到第一个等于6的元素呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length;

    while(left<right) {
        let mid = parseInt((right + left) / 2);
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left;
}

  • 为什么 while(left < right) 而不是 <= ?

    用相同的方法分析，因为 right = nums.length 而不是 nums.length - 1。因此每次循环的「搜索区间」是 [left, right) 左闭右开。

    while(left < right)终止的条件是 left == right，此时搜索区间 [left, left) 为空，所以可以正确终止。

  • 为什么没有返回 -1 的操作？如果 nums 中不存在 target 这个值，怎么办？

    对于这个数组，算法会返回 1。这个 1 的含义可以这样解读：nums 中小于 6 的元素有 1 个。

    比如对于有序数组 nums = [2,3,5,7], target = 1，算法会返回 0，含义是：nums 中小于 1的元素有 0 个。

    再比如说 nums 不变，target = 8，算法会返回 4，含义是：nums 中小于 8 的元素有 4 个。

    综上可以看出，函数的返回值（即 left 变量的值）取值区间是闭区间 [0, nums.length]，所以我 们简单添加两行代码就能在正确的时候 return -1：

    1
    2
    3
    4
    // target 比所有数都大
    if (left == nums.length) return -1;
    // 类似之前算法的处理方式
    return nums[left] == target ? left : -1;

  • 为什么 left = mid + 1，right = mid ？和之前的算法不一样？

    这个很好解释，因为我们的「搜索区间」是 [left, right) 左闭右开，所以当 nums[mid] 被检测之 后，下一步的搜索区间应该去掉 mid 分割成两个区间，即 [left, mid) 或 [mid + 1, right)。

  • 为什么该算法能够搜索左侧边界？

    关键在于对于 nums[mid] == target 这种情况的处理：

    1
    2
    if (nums[mid] == target)
        right = mid;

    可见，找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid)中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

查找最后一个等于给定元素的值(右边界)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function binarySearch(nums, target) {
    let left = 0;
    let right = nums.length;

    while(left<right) {
        let mid = parseInt((right + left) / 2);
        if (nums[mid] == target) {
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1;
}

  • 为什么最后返回 left - 1 而不像左侧边界的函数，返回 left？而且我觉得这里既然是搜索右侧边界，应该返回 right 才对。

    首先，while 循环的终止条件是 left == right，所以 left 和 right 是一样的，你非要体现右侧的特点，返回 right - 1 好了。

    因为我们对 left 的更新必须是 left = mid + 1，就是说 while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left-1] 可能是 target

学习心得

二分查找对于有序数组的查询效率非常高，但是对于边界问题处理上十分棘手，考察细节一不小心就会导致死循环，而且不易查找错误。

有效的理解是确定每次的搜索范围以及循环中止条件。对于每次修改搜索范围的原则是，关注mid有没有被搜索过。在此基础上+1或者-1。

参考资料