我之前寫過兩篇關(guān)于二分查找算法的文章,這篇算是一個(gè)小結(jié).我給這份文檔整理了一份pdf格式的文檔,可以在
這里下載.
二分查找算法學(xué)習(xí)札記
說明
作者:那誰(shuí)
blog: http://www.shnenglu.com/converse
轉(zhuǎn)載請(qǐng)注明出處.
二分查找算法基本思想
二分查找算法的前置條件是,一個(gè)已經(jīng)排序好的序列(在本篇文章中為了說明問題的方便,假設(shè)這個(gè)序列是升序排列的),這樣在查找所要查找的元素時(shí),首先與序列中間的元素進(jìn)行比較,如果大于這個(gè)元素,就在當(dāng)前序列的后半部分繼續(xù)查找,如果小于這個(gè)元素,就在當(dāng)前序列的前半部分繼續(xù)查找,直到找到相同的元素,或者所查找的序列范圍為空為止.
用偽代碼來表示, 二分查找算法大致是這個(gè)樣子的:
left = 0, right = n -1
while (left <= right)
mid = (left + right) / 2
case
x[mid] < t: left = mid + 1;
x[mid] = t: p = mid; break;
x[mid] > t: right = mid -1;
return -1;
第一個(gè)正確的程序
根據(jù)前面給出的算法思想和偽代碼, 我們給出第一個(gè)正確的程序,但是,它還有一些小的問題,后面會(huì)講到
int search(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n - 1;
while (left <= right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle;
}
else if (array[middle] < v)
{
left = middle;
}
else
{
return middle;
}
}
return -1;
}
下面,講講在編寫二分查找算法時(shí)可能出現(xiàn)的一些問題.
邊界錯(cuò)誤造成的問題
二分查找算法的邊界,一般來說分兩種情況,一種是左閉右開區(qū)間,類似于[left, right),一種是左閉右閉區(qū)間,類似于[left, right].需要注意的是, 循環(huán)體外的初始化條件,與循環(huán)體內(nèi)的迭代步驟, 都必須遵守一致的區(qū)間規(guī)則,也就是說,如果循環(huán)體初始化時(shí),是以左閉右開區(qū)間為邊界的,那么循環(huán)體內(nèi)部的迭代也應(yīng)該如此.如果兩者不一致,會(huì)造成程序的錯(cuò)誤.比如下面就是錯(cuò)誤的二分查找算法:
int search_bad(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n;
while (left < right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle - 1;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}
return -1;
}
這個(gè)算法的錯(cuò)誤在于, 在循環(huán)初始化的時(shí)候,初始化right=n,也就是采用的是左閉右開區(qū)間,而當(dāng)滿足array[middle] > v的條件是, v如果存在的話應(yīng)該在[left, middle)區(qū)間中,但是這里卻把right賦值為middle - 1了,這樣,如果恰巧middle-1就是查找的元素,那么就會(huì)找不到這個(gè)元素.
下面給出兩個(gè)算法, 分別是正確的左閉右閉和左閉右開區(qū)間算法,可以與上面的進(jìn)行比較:
int search2(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n - 1;
while (left <= right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle - 1;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}
return -1;
}
int search3(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n;
while (left < right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}
return -1;
}
死循環(huán)
上面的情況還只是把邊界的其中一個(gè)寫錯(cuò), 也就是右邊的邊界值寫錯(cuò), 如果兩者同時(shí)都寫錯(cuò)的話,可能會(huì)造成死循環(huán),比如下面的這個(gè)程序:
int search_bad2(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n - 1;
while (left <= right)
{
middle = (left + right) / 2;
if (array[middle] > v)
{
right = middle;
}
else if (array[middle] < v)
{
left = middle;
}
else
{
return middle;
}
}
return -1;
}
這個(gè)程序采用的是左閉右閉的區(qū)間.但是,當(dāng)array[middle] > v的時(shí)候,那么下一次查找的區(qū)間應(yīng)該為[middle + 1, right], 而這里變成了[middle, right];當(dāng)array[middle] < v的時(shí)候,那么下一次查找的區(qū)間應(yīng)該為[left, middle - 1], 而這里變成了[left, middle].兩個(gè)邊界的選擇都出現(xiàn)了問題, 因此,有可能出現(xiàn)某次查找時(shí)始終在這兩個(gè)范圍中輪換,造成了程序的死循環(huán).
溢出
前面解決了邊界選擇時(shí)可能出現(xiàn)的問題, 下面來解決另一個(gè)問題,其實(shí)這個(gè)問題嚴(yán)格的說不屬于算法問題,不過我注意到很多地方都沒有提到,我覺得還是提一下比較好.
在循環(huán)體內(nèi),計(jì)算中間位置的時(shí)候,使用的是這個(gè)表達(dá)式:
middle = (left + right) / 2;
假如,left與right之和超過了所在類型的表示范圍的話,那么middle就不會(huì)得到正確的值.
所以,更穩(wěn)妥的做法應(yīng)該是這樣的:
middle = left + (right - left) / 2;
更完善的算法
前面我們說了,給出的第一個(gè)算法是一個(gè)"正確"的程序, 但是還有一些小的問題.
首先, 如果序列中有多個(gè)相同的元素時(shí),查找的時(shí)候不見得每次都會(huì)返回第一個(gè)元素的位置, 比如考慮一種極端情況:序列中都只有一個(gè)相同的元素,那么去查找這個(gè)元素時(shí),顯然返回的是中間元素的位置.
其次, 前面給出的算法中,每次循環(huán)體中都有三次情況,兩次比較,有沒有辦法減少比較的數(shù)量進(jìn)一步的優(yōu)化程序?
<<編程珠璣>>中給出了解決這兩個(gè)問題的算法,結(jié)合前面提到溢出問題我對(duì)middle的計(jì)算也做了修改:
int search4(int array[], int n, int v)
{
int left, right, middle;
left = -1, right = n;
while (left + 1 != right)
{
middle = left + （right － left) / 2;
if (array[middle] < v)
{
left = middle;
}
else
{
right = middle;
}
}
if (right >= n || array[right] != v)
{
right = -1;
}
return right;
}
這個(gè)算法是所有這里給出的算法中最完善的一個(gè),正確,精確且效率高.
參考資料
1.<<編程珠璣>>
2.wiki上關(guān)于二分查找的說明:http://en.wikipedia.org/wiki/Binary_search