從零開始學演算法:4.二分查詢
作者: tiankonguse | 更新日期:
看完是不是發現二分查詢竟然如此簡單?
這篇文章涉及的原始碼可以全部免費獲得,在公眾號中回覆“二分查詢”可以獲得。
一、背景
大家好,我是tiankonguse。
由於某些原因,經常有人想學習演算法但之前又沒有相關經驗,不知道從何做起。
我思考了許久,計劃寫一個系列來分享如何入門學習演算法。
之前已經分享了《 認識演算法 》、《 瞭解套路長啥樣 》、《 排序演算法 》,這是第四篇。
本來還不知道分享什麼。工作中別人交接給我了一個專案,簡單看之後發現二分查詢演算法竟然寫錯了,雖然沒有死迴圈,但是查詢的定義不明確(有時候返回大於的值,有時候返回小於的值)。
這篇文章就分享一下二分查詢吧。
二、基本知識
二分查詢是一個很常見的演算法,主要用來在有序的陣列中查詢指定值的位置。
這個特定的含義不僅僅是等於,還可以是第一個大於和第一個大於等於的位置。
以數字為例,具體問題就是:
1.指定數字的位置?
2.首個大於等於指定數字的位置?
3.首個大於指定數字的位置?
4.最後一個小於指定數字的位置?
5.其他情況
正常情況下,我們可以通過遍歷有序陣列來做到這些,不過他們的複雜度將會是O(n)。
而二分查詢的思路是不斷的計算一箇中間節點,通過判斷中間階段快速將查詢空間減半。
下面以增序陣列為例,分別來看看各種情況吧。
三、查詢數字的位置
對於精確查詢位置這個,可能會面臨幾種情況:1.不存在,2.存在一個,3.存在多個。
所以問題又轉化為了查詢數字首次出現的位置 和 最後一個出現的位置。
先來看看首次出現的位置的程式碼吧。
我們可以定義left和right是全閉合的區間,這樣就可以精確的控制left和right的位置了。
如果mid小於value,可以確定答案肯定不在[left, mid],所以我們應該去[mid+1, right]查詢。
如果mid大於value,可以確定答案肯定不在[mid, right],所以我們應該去[left, mid-1]去查詢。
如果mid與value相等,我們就不好確定子區間如何劃分了。
不過還好,一般情況下 mid < right 的(思考題1:為什麼),所以我們可以大膽的把right設定為mid,使得區間範圍繼續變小。 只有一種情況下 mid 等於right,那就是 left 也等於 right,此時已經找到答案了。
而對於查詢最後一次出現的位置這個問題,只需要修改上圖的一行程式碼即可(思考題2:怎麼修改)。
四、查詢首個大於等於指定數字的位置
上面講的是等於的情況,對於不存在的返回了-1。
而對於大於等於的情況,其實會發現更簡單,不信看程式碼,和等於的少了幾行程式碼。
由於太簡單了,是不是都沒啥說的了。
五、查詢首個大於指定數字的位置
對於首個大於的數字的位置,你看完下面的程式碼肯定會驚呆的。
再給你們出個問題吧,這個程式碼與查詢首個大於等於的程式碼有什麼區別呢(思考題3)?
六、最後一個小於指定數字的位置
前面的兩個例子是首個小於和首個小於等於的,並且兩個程式碼極為相似。
所以這裡只展示一下最後一個小於的程式碼,而對於最後一個小於等於的,留作思考題,大家來思考下差異在哪裡(思考題4)。
對於最後一個小於的查詢,我們對區間的定義稍微變化一下,這裡改為右邊是開區間。
改之後,你會發現程式碼和上面的程式碼幾乎一樣。
這裡再出一道思考題,如果這裡使用閉區間會有什麼問題,該如何解決呢(思考題5)?
七、其他查詢情況
首個等於、最後一個等於、首個大於、首個大於等於 這四種情況看完了,其他的情況其實都是變種,不過對於 最後一個小於 我還是簡單介紹了。
下面來看看其他情況吧。
對於首個小於 或 首個小於等於的查詢,直接比較第一個即可。
對於最後一個大於 或 最後一個大於等於的查詢,直接比較最後一個即可。
對於最後一個小於的查詢,等價於首個大於等於的位置減1,當然不存在的需要特殊判斷(第六小節講解了)。
對於最後一個小於等於的查詢,等價於首個大於的位置減1,不存在的特殊判斷即可(第六小節修改一個地方)。
這樣我們就把增序的所有情況都分析完了。
回頭再看看上面的幾個程式碼,可以發現除了查詢等於的有點特殊,其他的都類似,模板如下:
總結一下就是這樣:
查詢首個或最後一個XX的問題,也就是查詢滿足需求的最小或最大位置問題。
根據 mid 不滿足需求的情況,我們可以直接確定其中邊界。
而對其其他的情況,我們需要判斷是否得到答案,沒得到則確定另一個邊界。
八、尾語
看完上面我整理的模板,是不是發現二分查詢竟然如此簡單?
不過有一點我還是需要強調一下。
對於首個相關的查詢,我們使用的右閉區間。
而對於最後一個相關的查詢,我們使用的是右開區間。
這樣做得目的是使得所有的查詢都最簡單。
當然所有地方都使用右閉區間 或 右開區間 也沒問題。
但是需要多考慮幾種情況,恰恰是這些情況,很多人考慮不充足導致二分查詢死迴圈。
另外有人可能發現了死迴圈,會加更多的特殊判斷,這樣雖然不會死迴圈了,但是可能導致二分查詢的定義不明確。
死迴圈和定義不明確是二分查詢最常見的問題,希望大家儘量能夠避免。
最後,上面給大家出的思考題希望大家也想想。
這篇文章涉及的原始碼可以全部免費獲得,在公眾號中回覆“二分查詢”可以獲得。
本文首發於公眾號:天空的程式碼世界,微信號:tiankonguse-code。
推薦閱讀:
今天長按識別上面的二維碼,在公眾號中回覆“ ACM模板 ”,你將免費獲得我大學耗時四年整理的《ACM演算法模板》。
回覆“ 演算法的世界 ”,或點選 閱讀原文 加入“tiankonguse的朋友們”,已有三百多個小夥伴加入。