二分查找的思想

提及二分查找算法，我想大部分人都不陌生，就算不是學(xué)計(jì)算機(jī)的，基本上也都使用過(guò)二分查找的思想，不信的話，且聽(tīng)我慢慢為你道來(lái)。

不知道你有沒(méi)有玩過(guò)這樣一個(gè)游戲，猜數(shù)字。就是說(shuō)一個(gè)人心里想了一個(gè)數(shù)字，這個(gè)數(shù)字有范圍，然后另外一個(gè)人去猜，每次猜的時(shí)候，另一個(gè)人會(huì)告訴你是猜的大了，還是小了，亦或是猜中了，看怎么樣才能夠最快的猜中另一個(gè)人想的數(shù)字。

想必大部分人都玩過(guò)吧，比如說(shuō)，數(shù)字范圍是 0 - 100，那我想你肯定是先猜 50，如果說(shuō)猜大了，那就去猜 25，否則去猜 75， 以此類推，直到被猜的區(qū)間長(zhǎng)度變?yōu)?1 或者你提前猜中了。

總結(jié)來(lái)說(shuō)，就是每次二分的過(guò)程中，將待查找的區(qū)間長(zhǎng)度變?yōu)樵瓉?lái)的一半，直到找到要查找的值或者區(qū)間當(dāng)中不存在待查找的值。

計(jì)算機(jī)中的二分查找算法

對(duì)應(yīng)到計(jì)算機(jī)當(dāng)中的二分查找算法又是啥樣的呢？那就是給定一個(gè)數(shù)組，然后查找值等于給定值的元素。說(shuō)到這，你是不是覺(jué)得二分查找很簡(jiǎn)單，沒(méi)必要單獨(dú)花一篇文章進(jìn)行講解？

我不能說(shuō)你理解的不對(duì)，確實(shí)，簡(jiǎn)單的二分查找算法挺簡(jiǎn)單的，但是你如果以為這就是全部的二分查找算法的話，那你就錯(cuò)了。

二分查找算法有很多變體問(wèn)題，這些問(wèn)題在生活當(dāng)中還非常常用，而且寫(xiě)起來(lái)非常燒腦。

唐納德.克努特 （Donald E.Knuth）在《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》的第 3 卷《排序和查找》中提到：

盡管第一個(gè)二分查找算法于 1946 年出現(xiàn)，然而第一個(gè)完全正確的二分查找算法實(shí)現(xiàn)直到 1962 年才出現(xiàn)。

如果你不知道唐納德.克努特的話，那你真的需要去補(bǔ)補(bǔ)計(jì)算機(jī)發(fā)展相關(guān)的知識(shí)了。

1. 今天呢，我先帶你了解下普通的二分查找算法怎么寫(xiě)。

2. 然后呢總結(jié)了四個(gè)典型的二分查找算法的變體問(wèn)題，分別是

   • 查找第一個(gè)值等于給定值的元素
   • 查找最后一個(gè)值等于給定值的元素
   • 查找第一個(gè)值大于給定值的元素
   • 查找最后一個(gè)值小于給定值的元素

普通的二分查找算法

普通的二分查找算法，就是給定一個(gè)沒(méi)有重復(fù)元素的有序數(shù)組，我們假定數(shù)組是升序排列的，然后查找值等于給定值的元素，找到的話，返回?cái)?shù)組的下標(biāo)，否則返回 -1。

image

如圖所示：在有序數(shù)組中 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
    # 循環(huán)終止條件
    while low <= high:
        # 計(jì)算 mid 的值，注意越界問(wèn)題
        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))

我想這個(gè)代碼對(duì)你來(lái)說(shuō)不是問(wèn)題，但還是有幾個(gè)需要注意的地方。

1. 循環(huán)終止條件，是 low <= high，不是 low < high,這個(gè)你可以這樣考慮，low 和 high 就代表了要查找區(qū)間的上下界，當(dāng) low == high 的時(shí)候，當(dāng)前區(qū)間長(zhǎng)度是 1,而不是 0。明白了這一點(diǎn)，你就能避免這個(gè)坑類。
2. 第二個(gè)坑是計(jì)算 mid 值的時(shí)候，對(duì)于一些其他的編程語(yǔ)言，比如 C、C++ 或者 Java 來(lái)說(shuō)容易出現(xiàn) low + high 大于 int 取值范圍的情況，雖然對(duì)于 Python 不會(huì)出現(xiàn)這樣的情況，但我還是建議你文中那樣寫(xiě)，給人的感覺(jué)就很有內(nèi)功修養(yǎng)。
3. 第三個(gè)就是 low 和 high 的更新。

以上呢，就是簡(jiǎn)單二分查找算法的一個(gè)寫(xiě)法，比較簡(jiǎn)單。接下來(lái)，我們就一起來(lái)看下二分查找的變體問(wèn)題。

查找第一個(gè)值等于給定值的元素

在這里呢，數(shù)組中的元素依然是有序的，但是存在重復(fù)元素，這樣的場(chǎng)景才更加符合真實(shí)場(chǎng)景。

image

如圖所示：在有序數(shù)組中 a[10] 查找第一個(gè)等于 3 的元素。

針對(duì)這個(gè)問(wèn)題，你可能會(huì)看到很多解法，說(shuō)實(shí)話，我也看了，但是他們都寫(xiě)的比較亂，從邏輯上理解起來(lái)有點(diǎn)困難，而且出了問(wèn)題很難調(diào)試。

代碼如下

#!/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:
            # 如果當(dāng)前值的下標(biāo)為 0， 或者其前一個(gè)下標(biāo)對(duì)應(yīng)的值不等于 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))

這個(gè)程序和上一個(gè)程序并沒(méi)有多大的區(qū)別，而且整體的邏輯非常清晰，唯一的改變就是如果當(dāng)前值與給定值相等的話，分兩種情況。

• 如果當(dāng)前值的下標(biāo)為 0 的話，那肯定就是它了
• 如果當(dāng)前值的下標(biāo)不為 0， 而且其前一個(gè)下標(biāo)對(duì)應(yīng)的值不等于給定值的話，那就是它了。

否則的話就說(shuō)明當(dāng)前值不是我們需要的，所以就需要 high = mid - 1 了。

查找最后一個(gè)值等于給定值的元素

image

如圖所示：在有序數(shù)組中 a[10] 查找最后一個(gè)等于 3 的元素。

如果你看懂并且理解了上面一個(gè)二分查找的變體問(wèn)題，那么這個(gè)其實(shí)和它是非常類似的，廢話不多說(shuō)，直接上代碼。

#!/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:
            # 如果當(dāng)前值的下標(biāo)是最后一個(gè)元素，或者其下一個(gè)下標(biāo)對(duì)應(yīng)的下標(biāo)值不等于給定值
            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))

是不是和上一個(gè)變體問(wèn)題的代碼很相似，所以只要把問(wèn)題分解開(kāi)來(lái)，不要總想著簡(jiǎn)潔，問(wèn)題就迎刃而解了。

查找第一個(gè)值大于給定值的元素

image

如圖所示：查找第一個(gè)值大于三的元素

代碼如下

#!/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)
        # 如果當(dāng)前值大于給定值，如果當(dāng)前值的下標(biāo)是0，或者不是 0 但是其前一個(gè)下標(biāo)對(duì)應(yīng)的值小于等于給定值
        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))

這個(gè)問(wèn)題和前面的不太一樣，這個(gè)需要查找第一個(gè)值大于給定值的元素，所以呢，自然程序和前面的就不太一樣了，這個(gè)需要分析的情況就是 array[mid] > target，剩下的情況就和上面的差不多了。

查找最后一個(gè)值小于給定值的元素

image

如圖所示：查找最后一個(gè)值小于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))

和上一個(gè)很相似，你學(xué)會(huì)了嗎？

總結(jié)

總結(jié)來(lái)看，二分查找算法的時(shí)間復(fù)雜度是 O(logn),非常高效的一種算法，但是必須依賴于底層數(shù)組這種數(shù)據(jù)結(jié)構(gòu)，因?yàn)閿?shù)組支持根據(jù)下標(biāo)隨機(jī)訪問(wèn)的特性。你看我寫(xiě)的代碼，可能感覺(jué)很簡(jiǎn)單，但是過(guò)一段時(shí)間來(lái)看的話，還是很容易忘的，只有真正的理解才能熟練運(yùn)用。而且二分查找算法和其他算法結(jié)合的也挺緊密的，比如說(shuō)貪心算法，前兩周我參加 LeetCode 周賽，碰到一道貪心的題目，幾分鐘就寫(xiě)完了，但是提交后發(fā)現(xiàn)超時(shí)了，也不知道如何進(jìn)行優(yōu)化，后來(lái)周賽結(jié)束查看別人的代碼才知道原來(lái)是二分算法和貪心算法的結(jié)合，直接裂開(kāi)。。。

好了，今天的文章就到這里了，不知道你對(duì)二分查找算法有沒(méi)有新的認(rèn)識(shí)呢？