二分查找（Binary Search）算法，也叫折半查找算法。二分查找的思想非常簡單，很多非計(jì)算機(jī)專業(yè)的同學(xué)很容易就能理解，但是看似越簡單的東西往往越難掌握好，想要靈活應(yīng)用就更加困難。
無處不在的二分思想
舉個(gè)例子：我們假設(shè)只有 10 個(gè)訂單，訂單金額分別是：8，11，19，23，27，33，45，55，67，98。 還是利用二分思想，每次都與區(qū)間的中間數(shù)據(jù)比對(duì)大小，縮小查找區(qū)間的范圍。為了更加直觀，我畫了一張查找過程的圖。其中，low 和 high 表示待查找區(qū)間的下標(biāo)，mid 表示待查找區(qū)間的中間元素下標(biāo)。
總結(jié)一下：二分查找針對(duì)的是一個(gè)有序的數(shù)據(jù)集合，查找思想有點(diǎn)類似分治思想。每次都通過跟區(qū)間的中間元素對(duì)比，將待查找的區(qū)間縮小為之前的一半，直到找到要查找的元素，或者區(qū)間被縮小為 0。
O(logn) 驚人的查找速度
二分查找是一種非常高效的查找算法，高效到什么程度呢？我們來分析一下它的時(shí)間復(fù)雜度。
我們假設(shè)數(shù)據(jù)大小是 n，每次查找后數(shù)據(jù)都會(huì)縮小為原來的一半，也就是會(huì)除以 2。最壞情況下，直到查找區(qū)間被縮小為空，才停止。
可以看出來，這是一個(gè)等比數(shù)列。其中 n/2k=1 時(shí)，k 的值就是總共縮小的次數(shù)。而每一次縮小操作只涉及兩個(gè)數(shù)據(jù)的大小比較，所以，經(jīng)過了 k 次區(qū)間縮小操作，時(shí)間復(fù)雜度就是 O(k)。通過 n/2k=1，我們可以求得 k=log2n，所以時(shí)間復(fù)雜度就是 O(logn)。
這是一種極其高效的時(shí)間復(fù)雜度，有的時(shí)候甚至比時(shí)間復(fù)雜度是常量級(jí) O(1) 的算法還要高效。為什么這么說呢？
因?yàn)閘ogn 是一個(gè)非?！翱植馈钡臄?shù)量級(jí)，即便n非常非常大，對(duì)應(yīng)的logn也很小。比如n等于2的32次方，這個(gè)數(shù)很大了吧?大約是42億。也就是說，如果我們在42億個(gè)數(shù)據(jù)中用二分查找一個(gè)數(shù)據(jù)，最多需要比較32次。
我們前面講過，用大0標(biāo)記法表示時(shí)間復(fù)雜度的時(shí)候，會(huì)省略掉常數(shù)、系數(shù)和低階。對(duì)于常量級(jí)時(shí)間復(fù)雜度的算法來說，0(1) 有可能表示的是一個(gè)非常大的常量值，比如O(1000)、O(10000)。 所以，常量級(jí)時(shí)間復(fù)雜度的算法有時(shí)候可能還沒有O(logn) 的算法執(zhí)行效率高。
二分查找的遞歸與非遞歸實(shí)現(xiàn)
實(shí)際上，簡單的二分查找并不難寫，注意我這里的“簡單”二字。下一節(jié)，我們會(huì)講到二分查找的變體問題，那才是真正燒腦的。今天，我們來看如何來寫最簡單的二分查找。
最簡單的情況就是有序數(shù)組中不存在重復(fù)元素，我們在其中用二分查找值等于給定值的數(shù)據(jù)。我用IOS代碼實(shí)現(xiàn)了一個(gè)最簡單的二分查找算法。
- (NSInteger)gly_bsearchWithLoop:(NSString *)propertyName value:(double)value
{
NSInteger low = 0;
NSInteger high = self.count - 1;
while (low <= high)
{
//為什么不寫(low + high) / 2，是因?yàn)槿绻?low 和 high 比較大的話，兩者之和就有可能會(huì)溢出。
NSInteger mid = low + ((high - low) >> 1);
double middleNumber = [[self[mid] valueForKey:propertyName] doubleValue];
if ([@(middleNumber) compare:@(value)] == NSOrderedSame)
{
return mid;
}
else if ([@(middleNumber) compare:@(value)] == NSOrderedAscending)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}
這個(gè)代碼我稍微解釋一下，low、high、mid 都是指數(shù)組下標(biāo)，其中 low 和 high 表示當(dāng)前查找的區(qū)間范圍，初始 low=0， high=n-1。mid 表示 [low, high] 的中間位置。我們通過對(duì)比 self[mid] 與value 的大小，來更新接下來要查找的區(qū)間范圍，直到找到或者區(qū)間縮小為 0。我就著重強(qiáng)調(diào)一下容易出錯(cuò)的 3 個(gè)地方。
1. 循環(huán)退出條件
注意是 low <= high，而不是 low < high。
2.mid的取值
實(shí)際上，mid=(low+high)/2 這種寫法是有問題的。因?yàn)槿绻鹟ow和high比較大的話，兩者之和就有可能會(huì)溢出。改進(jìn)的方法是將mid的計(jì)算方式寫成low+(high- -low)/2。更進(jìn)一步，如果要將性能優(yōu)化到極致的話，我們可以將這里的除以2操作轉(zhuǎn)化成位運(yùn)算low+((high-low)>>1)。因?yàn)橄啾瘸ㄟ\(yùn)算來說，計(jì)算機(jī)處理位運(yùn)算要快得多。
3.low和high的更新
low=mid+1, high=mid-1。 注意這里的+1和-1,如果直接寫成low=mid或者h(yuǎn)igh=mid,就可能,會(huì)發(fā)生死循環(huán)。比如，當(dāng)high=3, low=3 時(shí)，如果a[3]不等于value,就會(huì)導(dǎo)致一直循環(huán)不退出。
如果你留意我剛講的這三點(diǎn)，我想一個(gè)簡單的二分查找你已經(jīng)可以實(shí)現(xiàn)了。實(shí)際上，二分查找除了用循環(huán)來實(shí)現(xiàn)，還可以用遞歸來實(shí)現(xiàn)，過程也非常簡單。
- (NSInteger)gly_bsearchWithRecursion:(NSString *)propertyName value:(double)value
{
return [self gly_bsearchInternally:propertyName value:value low:0 high:self.count - 1];
}
- (NSInteger)gly_bsearchInternally:(NSString *)propertyName value:(double)value low:(NSInteger)low high:(NSInteger)high
{
if (low > high)
{
return -1;
}
//因?yàn)橄啾瘸ㄟ\(yùn)算來說，計(jì)算機(jī)處理位運(yùn)算要快得多。這里也等同于（NSInteger mid = low + (high - low) / 2）
NSInteger mid = low + ((high - low) >> 1);
double middleNumber = [[self[mid] valueForKey:propertyName] doubleValue];
if ([@(middleNumber) compare:@(value)] == NSOrderedSame)
{
return mid;
}
else if ([@(middleNumber) compare:@(value)] == NSOrderedAscending)
{
return [self gly_bsearchInternally:propertyName value:value low:mid + 1 high:high];
}
else
{
return [self gly_bsearchInternally:propertyName value:value low:low high:mid - 1];
}
}
二分查找應(yīng)用場景的局限性
前面我們分析過，二分查找的時(shí)間復(fù)雜度是O(logn),查找數(shù)據(jù)的效率非常高。不過，并不是什么情況下都可以用二分查找，它的應(yīng)用場景是有很大局限性的。那什么情況下適合用二分查找，什么情況下不適合呢?
首先，二分查找依賴的是順序表結(jié)構(gòu)，簡單點(diǎn)說就是數(shù)組。
那二分查找能否依賴其他數(shù)據(jù)結(jié)構(gòu)呢?比如鏈表。答案是不可以的，主要原因是二分查找算法需要按照下標(biāo)隨機(jī)訪問元素。我們在數(shù)組和鏈表那兩節(jié)講過，數(shù)組按照下標(biāo)隨機(jī)訪問數(shù)據(jù)的時(shí)間復(fù)雜度是0(1)，而鏈表隨機(jī)訪問的時(shí)間復(fù)雜度是O(n)。所以，如果數(shù)據(jù)使用鏈表存儲(chǔ)，- -分查找的時(shí)間復(fù)雜就會(huì)變得很高。
二分查找只能用在數(shù)據(jù)是通過順序表來存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)上。如果你的數(shù)據(jù)是通過其他數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)的，則無法應(yīng)用二分查找。
其次，二分查找針對(duì)的是有序數(shù)據(jù)。
二分查找對(duì)這一點(diǎn)的要求比較苛刻，數(shù)據(jù)必須是有序的。如果數(shù)據(jù)沒有序，我們需要先排序。前面章節(jié)里我們講到，排序的時(shí)間復(fù)雜度最低O(nlogn)，所以，如果我們針對(duì)的是-組靜態(tài)的數(shù)據(jù)，沒有頻繁地插入、刪除，我們可以進(jìn)行一次排序，多次二分查找。這樣排序的成本可被均攤,二分查找的邊際成本就會(huì)比較低。
但是，如果我們的數(shù)據(jù)集合有頻繁的插入和刪除操作，要想用二分查找，要么每次插入、刪除操作之后保證數(shù)據(jù)仍然有序，要么在每次二分查找之前都先進(jìn)行排序。針對(duì)這種動(dòng)態(tài)數(shù)據(jù)集合，無論哪種方法，維護(hù)有序的成本都是很高的。
所以，二分查找只能用在插入、刪除操作不頻繁，一 次排序多次查找的場景中。針對(duì)動(dòng)態(tài)變化的數(shù)據(jù)集合，二分查找將不再適用。那針對(duì)動(dòng)態(tài)數(shù)據(jù)集合，如何在其中快速查找某個(gè)數(shù)據(jù)呢?別急，等到二叉樹那一節(jié)我會(huì)詳細(xì)講。
再次，數(shù)據(jù)量太小不適合二分查找。
如果要處理的數(shù)據(jù)量很小，完全沒有必要用二分查找，順序遍歷就足夠了。比如我們在一個(gè)大小為10的數(shù)組中查找一個(gè)元素， 不管用二分查找還是順序遍歷，查找速度都差不多。只有數(shù)據(jù)量比較大的時(shí)候，二分查找的優(yōu)勢才會(huì)比較明顯。
不過，這里有一個(gè)例外。如果數(shù)據(jù)之間的比較操作非常耗時(shí)，不管數(shù)據(jù)量大小，我都推薦使用二分查找。比如，數(shù)組中存儲(chǔ)的都是長度超過300的字符串，如此長的兩個(gè)字符串之間比對(duì)大小，就會(huì)非常耗時(shí)。我們需要盡可能地減少比較次數(shù)，而比較次數(shù)的減少會(huì)大大提高性能，這個(gè)時(shí)候二分查找就比順序遍歷更有優(yōu)勢。
最后，數(shù)據(jù)量太大也不適合二分查找。
二分查找的底層需要依賴數(shù)組這種數(shù)據(jù)結(jié)構(gòu)，而數(shù)組為了支持隨機(jī)訪問的特性，要求內(nèi)存空間連續(xù)，對(duì)內(nèi)存的要求比較苛刻。比如，我們有1GB大小的數(shù)據(jù)，如果希望用數(shù)組來存儲(chǔ)，那就需要1GB的連續(xù)內(nèi)存空間。
注意這里的“連續(xù)”二字，也就是說，即便有2GB的內(nèi)存空間剩余，但是如果這剩余的2GB內(nèi)存空間都是零散的，沒有連續(xù)的1GB大小的內(nèi)存空間，那照樣無法申請(qǐng)一個(gè)1GB大小的數(shù)組。而我們的二分查找是作用在數(shù)組這種數(shù)據(jù)結(jié)構(gòu)之上的，所以太大的數(shù)據(jù)用數(shù)組存儲(chǔ)就比較吃力了，也就不能用二分查找了。
但是，上面介紹的只是最簡單的一種二分查找的代碼實(shí)現(xiàn)。接下來我們來講幾種二分查找的變形問題。
你可能會(huì)說，我們上面學(xué)的二分查找的代碼實(shí)現(xiàn)并不難寫啊。那是因?yàn)樯厦嬷v的只是二分查找中最簡單的一種情況，在不存在重復(fù)元素的有序數(shù)組中，查找值等于給定值的元素。最簡單的二分查找寫起來確實(shí)不難，但是，二分查找的變形問題就沒那么好寫了。
二分查找的變形問題很多，我只選擇幾個(gè)典型的來講解，其他的你可以借助我今天講的思路自己來分析。
變體一：查找第一個(gè)值等于給定值的元素
前面中的二分查找是最簡單的一種，即有序數(shù)據(jù)集合中不存在重復(fù)的數(shù)據(jù)，我們在其中查找值等于某個(gè)給定值的數(shù)據(jù)。如果我們將這個(gè)問題稍微修改下，有序數(shù)據(jù)集合中存在重復(fù)的數(shù)據(jù)，我們希望找到第一個(gè)值等于給定值的數(shù)據(jù)，這樣之前的二分查找代碼還能繼續(xù)工作嗎?
比如下面這樣一個(gè)有序數(shù)組， 其中，a[5], a[6]， a[7] 的值都等于8,是重復(fù)的數(shù)據(jù)。我們希望查找第一個(gè)等于8的數(shù)據(jù)，也就是下標(biāo)是5的元素。
如果我們用前面講的二分查找的代碼實(shí)現(xiàn)，首先拿8與區(qū)間的中間值a[4]比較，8比6大，于是在下標(biāo)5到9之間繼續(xù)查找。下標(biāo)5和9的中間位置是下標(biāo)7,a[7]正好等于8，所以代碼就返回了。
盡管a[7]也等于8,但它并不是我們想要找的第一個(gè)等于8的元素，因?yàn)榈谝粋€(gè)值等于8的元素是數(shù)組下標(biāo)為5的元素。我們前面講的二分查找代碼就無法處理這種情況了。所以，針對(duì)這個(gè)變形問題，我們可以稍微改造一下前面的代碼。
100個(gè)人寫二分查找就會(huì)有100種寫法。網(wǎng)上有很多關(guān)于變形二分查找的實(shí)現(xiàn)方法，有很多寫得非常簡潔，比如下面這個(gè)寫法。但是，盡管簡潔，理解起來卻非常燒腦，也很容易寫錯(cuò)。
- (NSInteger)gly_bsearchFirstItemWithLoop:(NSString *)propertyName value:(double)value
{
NSInteger low = 0;
NSInteger high = self.count - 1;
while (low <= high)
{
//為什么不寫(low + high) / 2，是因?yàn)槿绻?low 和 high 比較大的話，兩者之和就有可能會(huì)溢出。
NSInteger mid = low + ((high - low) >> 1);
double middleNumber = [[self[mid] valueForKey:propertyName] doubleValue];
if ([@(middleNumber) compare:@(value)] == NSOrderedDescending)
{
high = mid - 1;
}
else if ([@(middleNumber) compare:@(value)] == NSOrderedAscending)
{
low = mid + 1;
}
else
{
if (mid == 0 || [@([[self[mid - 1] valueForKey:propertyName] doubleValue]) compare:@(value)] != NSOrderedSame)
{
return mid;
}
else
{
high = mid - 1;
}
}
}
return -1;
}
我來稍微解釋一下 這段代碼。self[mid] 跟要查找的value的大小關(guān)系有三種情況:大于、小于、等于。對(duì)于self[mid]>value的情況，我們需要更新high= mid-1;對(duì)于self[mid]<value的情況，我們需要更新low=mid+1。這兩點(diǎn)都很好理解。那當(dāng)self[mid]=value的時(shí)候應(yīng)該如何處理呢?
如果我們查找的是任意一個(gè)值等于給定值的元素，當(dāng)self[mid]等于要查找的值時(shí)，self[mid] 就是我們要找的元素。但是，如果我們求解的是第一個(gè)值等于給定值的元素，當(dāng)self[mid]等于要查找的值時(shí)，我們就需要確認(rèn)一下這個(gè)self[mid]是不是第一個(gè)值等于給定值的元素。
我們重點(diǎn)看一下if (mid == 0 || [@([[self[mid - 1] valueForKey:propertyName] doubleValue]) compare:@(value)] != NSOrderedSame)。如果mid等于0，那這個(gè)元素已經(jīng)是數(shù)組的第一個(gè)元素，那它肯定是我們要找的;如果mid不等于0,但self[mid]的前一個(gè)元素self[mid-1]不等于value,那也說明self[mid]就是我們要找的第一個(gè)值等于給定值的元素。
如果經(jīng)過檢查之后發(fā)現(xiàn)self[mid]前面的一個(gè)元素self[mid-1]也等于value,那說明此時(shí)的self[mid]肯定不是我們要查找的第一一個(gè)值等于給定值的元素。那我們就更新high=mid-1,因?yàn)橐业脑乜隙ǔ霈F(xiàn)在[low, mid-1]之間。
對(duì)比上面的兩段代碼，是不是下面那種更好理解?實(shí)際上，很多人都覺得變形的二分查找很難寫,主要原因是太追求第一種那樣完美、簡潔的寫法。而對(duì)于我們做工程開發(fā)的人來說，代碼易讀懂、沒Bug,其實(shí)更重要，所以我覺得第二種寫法更好。
變體二：查找最后一個(gè)值等于給定值的元素
前面的問題是查找第一個(gè)值等于給定值的元素，我現(xiàn)在把問題稍微改一下，查找最后一個(gè)值等于給定值的元素，又該如何做呢？如果你掌握了前面的寫法，那這個(gè)問題你應(yīng)該很輕松就能解決。你可以先試著實(shí)現(xiàn)一下，然后跟我寫的對(duì)比一下。
- (NSInteger)gly_bsearchLastItemWithLoop:(NSString *)propertyName value:(double)value
{
NSInteger low = 0;
NSInteger high = self.count - 1;
while (low <= high)
{
//為什么不寫(low + high) / 2，是因?yàn)槿绻?low 和 high 比較大的話，兩者之和就有可能會(huì)溢出。
NSInteger mid = low + ((high - low) >> 1);
double middleNumber = [[self[mid] valueForKey:propertyName] doubleValue];
if ([@(middleNumber) compare:@(value)] == NSOrderedDescending)
{
high = mid - 1;
}
else if ([@(middleNumber) compare:@(value)] == NSOrderedAscending)
{
low = mid + 1;
}
else
{
if (mid == self.count - 1 || [@([[self[mid + 1] valueForKey:propertyName] doubleValue]) compare:@(value)] != NSOrderedSame)
{
return mid;
}
else
{
low = mid + 1;
}
}
}
return -1;
}
我們還是重點(diǎn)看第11行代碼。如果a[mid]這個(gè)元素已經(jīng)是數(shù)組中的最后一個(gè)元素了，那它肯定是我們要找的;如果a[mid]的后一個(gè)元素a[mid+1]不等于value,那也說明a[mid]就是我們要找的最后一個(gè)值等于給定值的元素。
如果我們經(jīng)過檢查之后，發(fā)現(xiàn)a[mid]后面的一個(gè)元素a[mid+1]也等于value,那說明當(dāng)前的這個(gè)a[mid]并不是最后一個(gè)值等于給定值的元素。我們就更新low=mid+1,因?yàn)橐业脑乜隙ǔ霈F(xiàn)在[mid+1, high]之間。
變體三:查找第一個(gè)大于等于給定值的元素
現(xiàn)在我們再來看另外- -類變形問題。在有序數(shù)組中，查找第一個(gè)大于等 于給定值的元素。比如，數(shù)組中存儲(chǔ)的這樣一個(gè)序列: 3, 4，6，7, 10。如果查找第一個(gè)大于等于5的元素，那就是6。
實(shí)際上，實(shí)現(xiàn)的思路跟前面的那兩種變形問題的實(shí)現(xiàn)思路類似，代碼寫起來甚至更簡潔。
- (NSInteger)gly_bsearchMoreWithLoop:(NSString *)propertyName value:(double)value
{
NSInteger low = 0;
NSInteger high = self.count - 1;
while (low <= high)
{
NSInteger mid = low + ((high - low) >> 1);
double middleNumber = [[self[mid] valueForKey:propertyName] doubleValue];
if ([@(middleNumber) compare:@(value)] == NSOrderedAscending)
{
low = mid + 1;
}
else
{
if (mid == 0 || [@([[self[mid - 1] valueForKey:propertyName] doubleValue]) compare:@(value)] == NSOrderedAscending)
{
return mid;
}
else
{
high = mid - 1;
}
}
}
return -1;
}
如果self[mid]小于要查找的值value,那要查找的值肯定在[mid+1, high]之間，所以，我們更新low=mid+1。
對(duì)于self[mid]大于等于給定值value的情況，我們要先看下這個(gè)self[mid]是不是我們要找的第一個(gè)值大于等于給定值的元素。如果a[mid]前面已經(jīng)沒有元素，或者前面一個(gè)元素小于要查找的值value,那self[mid]就是我們要找的元素。這段邏輯對(duì)應(yīng)的代碼是if (mid == 0 || [@([[self[mid - 1] valueForKey:propertyName] doubleValue]) compare:@(value)] == NSOrderedAscending)這行。
如果self[mid-1]也大于等于要查找的值value,那說明要查找的元素在[low, mid-1]之間，所以,我們將high更新為mid-1。
變體四:查找最后一個(gè)小于等于給定值的元素
現(xiàn)在，我們來看最后一種二分查找的變形問題，查找最后一個(gè)小于等于給定值的元素。比如，數(shù)組中存儲(chǔ)了這樣一組數(shù)據(jù): 3, 5, 6, 8, 9, 10。最后一一個(gè)小于等于7的元素就是6。是不是有點(diǎn)類似上面那一種?實(shí)際上，實(shí)現(xiàn)思路也是一樣的。
有了前面的基礎(chǔ)，你完全可以自己寫出來了，所以我就不詳細(xì)分析了。我把代碼貼出來，你可以寫完之后對(duì)比一下。
- (NSInteger)gly_bsearchLessWithLoop:(NSString *)propertyName value:(double)value
{
NSInteger low = 0;
NSInteger high = self.count - 1;
while (low <= high)
{
NSInteger mid = low + ((high - low) >> 1);
double middleNumber = [[self[mid] valueForKey:propertyName] doubleValue];
if ([@(middleNumber) compare:@(value)] == NSOrderedDescending)
{
high = mid - 1;
}
else
{
if (mid == self.count - 1 || [@([[self[mid + 1] valueForKey:propertyName] doubleValue]) compare:@(value)] == NSOrderedDescending)
{
return mid;
}
else
{
low = mid + 1;
}
}
}
return -1;
}
內(nèi)容小結(jié)
前面我說過，凡是用二分查找能解決的，絕大部分我們更傾向于用散列表或者二叉查找樹。即便是二分查找在內(nèi)存使用上更節(jié)省，但是畢竟內(nèi)存如此緊缺的情況并不多。那二分查找真的沒什么用處了嗎?
實(shí)際上，前面講的求“值等于給定值”的二分查找確實(shí)不怎么會(huì)被用到，二分查找更適合用在“近似”查找問題，在這類問題上，二分查找的優(yōu)勢更加明顯。比如今天講的這幾種變體問題，用其他數(shù)據(jù)結(jié)構(gòu)，比如散列表、二叉樹，就比較難實(shí)現(xiàn)了。
變體的二分查找算法寫起來非常燒腦，很容易因?yàn)榧?xì)節(jié)處理不好而產(chǎn)生Bug，這些容易出錯(cuò)的細(xì)節(jié)有:終止條件、區(qū)間上下界更新方法、返回值選擇。所以今天的內(nèi)容你最好能用自己實(shí)現(xiàn)一遍，對(duì)鍛煉編碼能力、邏輯思維、寫出Bug free代碼，會(huì)很有幫助。
最后：
自己寫了一個(gè)NSArray+GLYLookup算法分類，只需1行代碼，即可完成快速查找。
