五千字長文帶你學(xué)習(xí) 二分查找算法

二分查找的思想

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

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

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

總結(jié)來說，就是每次二分的過程中，將待查找的區(qū)間長度變?yōu)樵瓉淼囊话耄钡秸业揭檎业闹祷蛘邊^(qū)間當(dāng)中不存在待查找的值。

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

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

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

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

唐納德.克努特 （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. 今天呢，我先帶你了解下普通的二分查找算法怎么寫。

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

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

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

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

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

普通的二分查找算法

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

如圖所示：在有序數(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?的值，注意越界問題
????????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ì)你來說不是問題，但還是有幾個(gè)需要注意的地方。

1. 循環(huán)終止條件，是 low <= high，不是 low < high,這個(gè)你可以這樣考慮，low 和 high 就代表了要查找區(qū)間的上下界，當(dāng) low == high 的時(shí)候，當(dāng)前區(qū)間長度是 1,而不是 0。明白了這一點(diǎn)，你就能避免這個(gè)坑類。

2. 第二個(gè)坑是計(jì)算 mid 值的時(shí)候，對(duì)于一些其他的編程語言，比如 C、C++ 或者 Java 來說容易出現(xiàn) low + high 大于 int 取值范圍的情況，雖然對(duì)于 Python 不會(huì)出現(xiàn)這樣的情況，但我還是建議你文中那樣寫，給人的感覺就很有內(nèi)功修養(yǎng)。

3. 第三個(gè)就是 low 和 high 的更新。

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

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

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

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

針對(duì)這個(gè)問題，你可能會(huì)看到很多解法，說實(shí)話，我也看了，但是他們都寫的比較亂，從邏輯上理解起來有點(diǎ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]?????????????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è)程序并沒有多大的區(qū)別，而且整體的邏輯非常清晰，唯一的改變就是如果當(dāng)前值與給定值相等的話，分兩種情況。

• 如果當(dāng)前值的下標(biāo)為 0 的話，那肯定就是它了

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

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

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

如果你看懂并且理解了上面一個(gè)二分查找的變體問題，那么這個(gè)其實(shí)和它是非常類似的。

如圖所示：在有序數(shù)組?a[10]?中查找最后一個(gè)等于 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]?????????????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è)變體問題的代碼很相似，所以只要把問題分解開來，不要總想著簡潔，問題就迎刃而解了。

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

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

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

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

且聽我下篇文章為你講解如何將二分算法和貪心算法進(jìn)行結(jié)合。

好了，今天的文章就到這里了，不知道你對(duì)二分查找算法有沒有新的認(rèn)識(shí)呢，如果有問題的話，歡迎在微信公眾號(hào)底部找到我的聯(lián)系方式，和我進(jìn)行交流，我們共同進(jìn)步。