几种二分查找的模板与理解

编程算法

字数统计: 1.5k阅读时长: 6 min

 2020/04/29   Share

前言

二分查找是常见的一种搜索方式，通常用在顺序列表中查找特定的数或者区间，虽然看起来十分简单，但是在写代码的时候极容易出错，原因在于边界判断上，本质上还是对二分查找理解不到位。这篇文章整理下二分查找的模板以及谈谈自己的理解。

实践

大体框架

def binarySearch(nums,target):
    left = 0
    right = ...
    while (...):
        mid = (left + right) // 2
        if nums[mid] == target:
            ...
        elif nums[mid] < target:
            left = ...
        elif nums[mid] > target:
            right = ...
    return ...

二分查找的模板大致如上，其中…表示需要注意的地方。在写二分查找时尽量将所有情况都用else if的形式写出来，直观一些。
其次在一些语言中，使用left+right有可能会溢出，所以可以改写成left + (right - left) // 2。
基于以上模板，我们可以详细分为几类。

寻找特定的一个数

这个是我们常用到的，即在数组中寻找一个特定的数，前提是这个数组已经采用升序排序。

def binarySearch(nums,target):
    left = 0
    right = len(nums) - 1
    while (left <= right):
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
    return -1

这里需要注意的有：

Q：为什么while的条件是left <= right，而不是left < right？
A：当条件为<=时，相当于搜索的是[left,right]区间，而<则相当于[left,right)的区间，当right的取值为len(nums)时，我们的nums[right]是越界的，此时右区间需要开。
<=的终止条件为left == right + 1，此时区间为[right+1,right]，区间为空。
< 的终止条件为left == right，即[left,left)，只有一个数的区间，但此时这个数并没有被扫描到，所以使用<作为判断的话需要加入一个判断语句if nums[left] == target left else -1
Q：left 和 right 到底需要怎么改变？
A：上述代码中left=mid+1与right=mid-1是因为我们已经明确搜索区间是闭区间，即左右边界都已经搜索过，或者说mid这个索引的数已经被搜索过，所以我们需要根据需要在mid的左右区间进行搜索，即[left,mid-1]或者[mid+1,right]。

寻找左边界的二分查找

如果一个数组存在重复元素，并且需要你返回第一个出现这个数的索引，那么显然我们使用普通的二分查找并不能获得这个元素的在数组中出现的左边界。
我们先给出使用left < right为条件的代码

def left_bound(nums,target):
    left = 0
    right = len(nums)
    while (left < rgiht):
        mid = (left + right) // 2
        if nums[mid] == target:
            right = mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid
    return left

这个代码是许多人常用来搜索左边界的代码，但是在结果返回时存在着一个问题。我们先整理一下问题:

Q：如果数组中不存在这个数，那么返回不就不对了吗？
A：确实如此。我们刚才说到，使用<为条件的搜索为右开区间，当退出循环时，此时区间为[left,left)，并且left的取值有可能为数组边界,所以我们需要两个判断语句，
1
2
3
4
if left == len(nums) or nums[left] != target:
return -1
else:
return left
Q：为啥是left < right?
A：理由同上，因为right被初始化为len(nums)，需要采用右开区间保证下标不越界。
Q：为什么left = mid + 1,right = mid?
A：因为是左闭右开区间，需要将区间分为[left,mid)与[mid+1,right)。

Q：能不能统一为left<=right?
A：我个人认为统一left <= right 比较好，前提是理解了搜索区间这个概念。

def left_bound(nums,target):
    left = 0
    right = len(nums)-1
    while (left <= right):
        mid = (left + right) // 2
        if nums[mid] == target:
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
    if left >= len(nums) or nums[left] != target:
        return -1
    return left

寻找右边界的二分查找

与上面代码类似，这里我只写出left<=right为条件的代码。

def right_bound(nums,target):
    left = 0
    right = len(nums)-1
    while (left <= right):
        mid = (left + right) // 2
        if nums[mid] == target:
            left = mid + 1
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
    if right < 0 or nums[right] != target:
        return -1
    return right

注意的点为：

搜索左右边间的区别在于当nums[mid] == target时需要缩小哪个边界，当我们需要寻找左侧边界时，我们应该在搜索到target后，去搜索左侧区间；而当我们需要寻找右侧边界时，在搜索到target时，去寻找右区间。
之所以检测right是因为right的取值为[-1,len(nums)-1]，即当target比所有元素小时，right会减至-1，需要防止越界。

总结

我们明确搜索区间概念之后，统一将条件写为left<=right，并从中总结规律。
先是二分查找

def binarySearch(nums,target):
    left = 0
    right = len(nums) - 1
    while (left <= right):
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
    return -1

其次寻找左边界

def left_bound(nums,target):
    left = 0
    right = len(nums)-1
    while (left <= right):
        mid = (left + right) // 2
        if nums[mid] == target:
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
    if left >= len(nums) or nums[left] != target:
        return -1
    return left

最后是寻找右边界

def right_bound(nums,target):
    left = 0
    right = len(nums)-1
    while (left <= right):
        mid = (left + right) // 2
        if nums[mid] == target:
            left = mid + 1
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
    if right < 0 or nums[right] != target:
        return -1
    return right

寻找左右边界区别在于nums[mid] == target时需要收缩左侧边界还是右侧边界，还有因为left属于[0,len(nums)]，right属于[-1,len(nums)-1]，所以需要判断各自越界情况。
这些便是从升序数组中二分查找的方法。如果理解了这些，那降序数组的二分搜索也是万变不离其宗的。

原文作者：Zer0e

原文链接：https://re0.top/2020/04/29/binary_search/

发表日期：四月 29日 2020, 4:10:00 下午

更新日期：May 2nd 2020, 11:44:50 pm

Next Post

TopK问题与快速选择算法
Previous Post

浅谈动态规划

CATALOG

1. 前言
2. 实践
3. 总结

