五千字长文带你学习二分查找算法及其变体

关注
发布于: 2020 年 11 月 29 日
二分查找的思想﻿
提及二分查找算法，我想大部分人都不陌生，就算不是学计算机的，基本上也都使用过二分查找的思想，不信的话，且听我慢慢为你道来。
﻿
不知道你有没有玩过这样一个游戏，猜数字。就是说一个人心里想了一个数字，这个数字有范围，然后另外一个人去猜，每次猜的时候，另一个人会告诉你是猜的大了，还是小了，亦或是猜中了，看怎么样才能够最快的猜中另一个人想的数字。
﻿
想必大部分人都玩过吧，比如说，数字范围是 0 - 100，那我想你肯定是先猜 50，如果说猜大了，那就去猜 25，否则去猜 75， 以此类推，直到被猜的区间长度变为 1 或者你提前猜中了。
﻿
总结来说，就是每次二分的过程中，将待查找的区间长度变为原来的一半，直到找到要查找的值或者区间当中不存在待查找的值。
﻿
计算机中的二分查找算法﻿
对应到计算机当中的二分查找算法又是啥样的呢？那就是给定一个数组，然后查找值等于给定值的元素。说到这，你是不是觉得二分查找很简单，没必要单独花一篇文章进行讲解？
﻿
我不能说你理解的不对，确实，简单的二分查找算法挺简单的，但是你如果以为这就是全部的二分查找算法的话，那你就错了。
﻿
二分查找算法有很多变体问题，这些问题在生活当中还非常常用，而且写起来非常烧脑。
﻿
唐纳德.克努特 （Donald E.Knuth）在《计算机程序设计艺术》的第 3 卷《排序和查找》中提到：
﻿
>尽管第一个二分查找算法于 1946 年出现，然而第一个完全正确的二分查找算法实现直到 1962 年才出现。
﻿
如果你不知道唐纳德.克努特的话，那你真的需要去补补计算机发展相关的知识了。
﻿
今天呢，我先带你了解下普通的二分查找算法怎么写。
   
然后呢总结了四个典型的二分查找算法的变体问题，分别是
﻿
   + 查找第一个值等于给定值的元素
   + 查找最后一个值等于给定值的元素
   + 查找第一个值大于给定值的元素
   + 查找最后一个值小于给定值的元素
﻿
普通的二分查找算法﻿
普通的二分查找算法，就是给定一个没有重复元素的有序数组，我们假定数组是升序排列的，然后查找值等于给定值的元素，找到的话，返回数组的下标，否则返回 -1。
﻿
﻿
如图所示：在有序数组中 a[10] 查找 5、11。
﻿
代码如下
#!/usr/bin/python
# -*- coding:utf-8 -*-
from typing import List
def search(array: List[int], target: int) -> int:
    low, high = 0, len(array) - 1
    # 循环终止条件
    while low <= high:
        # 计算 mid 的值，注意越界问题
        mid = low + ((high - low) >> 1)
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            # high 的更新
            high = mid - 1
        else:
            # low 的更新
            low = mid + 1
    return -1
if __name__ == "__main__":
    array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    target = 5
    print(search(array, target))
    print("------")
    target = 11
    print(search(array, target))
﻿
我想这个代码对你来说不是问题，但还是有几个需要注意的地方。
﻿
循环终止条件，是 low <= high，不是 low < high,这个你可以这样考虑，low 和 high 就代表了要查找区间的上下界，当 low == high 的时候，当前区间长度是 1,而不是 0。明白了这一点，你就能避免这个坑类。
第二个坑是计算 mid 值的时候，对于一些其他的编程语言，比如 C、C++ 或者 Java 来说容易出现 low + high 大于 int 取值范围的情况，虽然对于 Python 不会出现这样的情况，但我还是建议你文中那样写，给人的感觉就很有内功修养。
第三个就是 low 和 high 的更新。
﻿
以上呢，就是简单二分查找算法的一个写法，比较简单。接下来，我们就一起来看下二分查找的变体问题。
﻿
查找第一个值等于给定值的元素﻿
在这里呢，数组中的元素依然是有序的，但是存在重复元素，这样的场景才更加符合真实场景。
﻿
﻿
如图所示：在有序数组中 a[10] 查找第一个等于 3 的元素。
﻿
针对这个问题，你可能会看到很多解法，说实话，我也看了，但是他们都写的比较乱，从逻辑上理解起来有点困难，而且出了问题很难调试。
﻿
代码如下﻿
#!/usr/bin/python
# -*- coding:utf-8 -*-
from typing import List
def search_first_equal_target(array: List[int], target: int) -> int:
    low, high = 0, len(array) - 1
    while low <= high:
        mid = low + ((high - low) >> 1)
        if array[mid] > target:
            high = mid - 1
        elif array[mid] < target:
            low = mid + 1
        else:
            # 如果当前值的下标为 0， 或者其前一个下标对应的值不等于 target
            if (mid == 0) or (array[mid - 1] != target):
                return mid
            else:
                high = mid - 1
    return -1
if __name__ == "__main__":
    array = [1, 2, 3, 3, 3, 3, 3, 3, 9, 10]
    target = 3
    print(search_first_equal_target(array, target))
这个程序和上一个程序并没有多大的区别，而且整体的逻辑非常清晰，唯一的改变就是如果当前值与给定值相等的话，分两种情况。
  
如果当前值的下标为 0 的话，那肯定就是它了
如果当前值的下标不为 0， 而且其前一个下标对应的值不等于给定值的话，那就是它了。
﻿
否则的话就说明当前值不是我们需要的，所以就需要 high = mid - 1 了。
﻿
查找最后一个值等于给定值的元素
如图所示：在有序数组中 a[10] 查找最后一个等于 3 的元素。
﻿
如果你看懂并且理解了上面一个二分查找的变体问题，那么这个其实和它是非常类似的，废话不多说，直接上代码。
﻿
#!/usr/bin/python
# -*- coding:utf-8 -*-
from typing import List
def search_last_equal_target(array: List[int], target: int) -> int:
    low, high = 0, len(array) - 1
    while low <= high:
        mid = low + ((high - low) >>1)
        if array[mid] > target:
            high = mid - 1
        elif array[mid] < target:
            low = mid + 1
        else:
            # 如果当前值的下标是最后一个元素，或者其下一个下标对应的下标值不等于给定值
            if (mid == len(array) - 1) or (array[mid + 1] != target):
                return mid
            else:
                low = mid + 1
    return -1
if __name__ == "__main__":
    array = [1, 2, 3, 3, 3, 3, 3, 3, 9, 10]
    target = 3
    print(search_last_equal_target(array, target))
是不是和上一个变体问题的代码很相似，所以只要把问题分解开来，不要总想着简洁，问题就迎刃而解了。
﻿
查找第一个值大于给定值的元素
﻿
如图所示：查找第一个值大于三的元素
﻿
代码如下﻿
#!/usr/bin/python
# -*- coding:utf-8 -*-
from typing import List
def search_first_greater_target(array: List[int], target: int):
    low, high = 0, len(array) - 1
    while low <= high:
        mid = low + ((high - low) >> 1)
        # 如果当前值大于给定值，如果当前值的下标是0，或者不是 0 但是其前一个下标对应的值小于等于给定值
        if array[mid] > target:
            if (mid == 0) or (array[mid - 1] <= target):
                return mid
            else:
                high = mid - 1
        else:
            low = mid + 1
    return -1
if __name__ == "__main__":
    array = [1, 2, 3, 3, 3, 3, 3, 3, 9, 10]
    target = 3
    print(search_first_greater_target(array, target))
这个问题和前面的不太一样，这个需要查找第一个值大于给定值的元素，所以呢，自然程序和前面的就不太一样了，这个需要分析的情况就是 array[mid] > target，剩下的情况就和上面的差不多了。
﻿
查找最后一个值小于给定值的元素
﻿
如图所示：查找最后一个值小于3的元素
﻿
#!/usr/bin/python
# -*- coding:utf-8 -*-
from typing import List
def search_last_less_equal(array: List[int], target:int) -> int:
    low, high = 0, len(array) - 1
    while low <= high:
        mid = low + ((high - low) >> 1)
        if array[mid] >= target:
            high = mid - 1
        else:
            if (mid == len(array) - 1) or (array[mid + 1] >= target):
                return mid
            else:
                low = mid + 1
    return -1
if __name__ == "__main__":
    array = [1, 2, 3, 3, 3, 3, 3, 3, 9, 10]
    target = 3
    print(search_last_less_equal(array, target))
﻿
和上一个很相似，你学会了吗？
﻿
总结﻿
总结来看，二分查找算法的时间复杂度是 O(logn),非常高效的一种算法，但是必须依赖于底层数组这种数据结构，因为数组支持根据下标随机访问的特性。你看我写的代码，可能感觉很简单，但是过一段时间来看的话，还是很容易忘的，只有真正的理解才能熟练运用。而且二分查找算法和其他算法结合的也挺紧密的，比如说贪心算法，前两周我参加 LeetCode 周赛，碰到一道贪心的题目，几分钟就写完了，但是提交后发现超时了，也不知道如何进行优化，后来周赛结束查看别人的代码才知道原来是二分算法和贪心算法的结合，直接裂开。。。
﻿
今天的文章来自我听了极客时间王争老师的专栏《数据结构与算法之美》中二分查找算法之后做的总结，如果你还没听过王争老师的专栏的话，推荐你去听下，真的很不错，良心推荐。
﻿
好了，今天的文章就到这里了，不知道你对二分查找算法有没有新的认识呢？如果有问题的话，欢迎关注我的微信公众号「与你一起学算法」，同时可以在微信公众号底部找到我的联系方式，和我进行交流，我们共同进步。我一直坚信一个人可以走的更快，一群人可以走的更远。
﻿