【44期】盤點那些必問的數(shù)據(jù)結構算法題之二分查找算法

程序員的成長之路

互聯(lián)網/程序員/技術/資料共享?

閱讀本文大概需要 7 分鐘。

來自：juejin.im/post/5baba2eaf265da0aea698244

0 概述

二分查找本身是個簡單的算法，但是正是因為其簡單，更容易寫錯。甚至于在二分查找算法剛出現(xiàn)的時候，也是存在bug的（溢出的bug），這個bug直到幾十年后才修復（見《編程珠璣》）。

本文打算對二分查找算法進行總結，并對由二分查找引申出來的問題進行分析和匯總。若有錯誤，請指正。

1 二分查找基礎

相信大家都知道二分查找的基本算法，如下所示，這就是二分查找算法代碼：

/**
?*?基本二分查找算法
?*/
int?binarySearch(int?a[],?int?n,?int?t)
{
????int?l?=?0,?u?=?n?-?1;
????while?(l?<=?u)?{
????????int?m?=?l?+?(u?-?l)?/?2;?//?同（l+u）/?2，這里是為了防溢出
????????if?(t?>?a[m])
????????????l?=?m?+?1;
????????else?if?(t?????????????u?=?m?-?1;
????????else
????????????return?m;
????}
????return?-(l+1);
}

算法的思想就是：從數(shù)組中間開始，每次排除一半的數(shù)據(jù)，時間復雜度為O(lgN)。這依賴于數(shù)組有序這個性質。如果t存在數(shù)組中，則返回t在數(shù)組的位置；否則，不存在則返回-(l+1)。

這里需要解釋下為什么t不存在數(shù)組中時不是返回-1而要返回-(l+1)。首先我們可以觀察 l 的值，如果查找不成功，則 l 的值恰好是 t 應該在數(shù)組中插入的位置。

舉個例子，假定有序數(shù)組a={1, 3, 4, 7, 8}， 那么如果t=0，則顯然t不在數(shù)組中，則二分查找算法最終會使得l=0 > u=-1退出循環(huán)；如果t=9，則t也不在數(shù)組中，則最后l=5 > u=4退出循環(huán)。如果t=5，則最后l=3 > u=2退出循環(huán)。

因此在一些算法中，比如DHT（一致性哈希）中，就需要這個返回值來使得新加入的節(jié)點可以插入到合適的位置中，在求最長遞增子序列的NlgN算法中，也用到了這一點，參見:

http://blog.csdn.net/ssjhust123/article/details/7798737

還有一個小點就是之所以返回-(l+1)而不是直接返回 -l 是因為 l 可能為0，如果直接返回 -l 就無法判斷是正常返回位置0還是查找不成功返回的0。

2 查找有序數(shù)組中數(shù)字第一次出現(xiàn)位置

現(xiàn)在考慮一個稍微復雜點的問題，如果有序數(shù)組中有重復數(shù)字，比如數(shù)組a={1, 2, 3, 3, 5, 7, 8}，需要在其中找出3第一次出現(xiàn)的位置。這里3第一次出現(xiàn)位置為2。這個問題在《編程珠璣》第九章有很好的分析，這里就直接用了。

算法的精髓在于循環(huán)不變式的巧妙設計，代碼如下：

/**
?*?二分查找第一次出現(xiàn)位置
?*/
int?binarySearchFirst(int?a[],?int?n,?int?t)
{
????int?l?=?-1,?u?=?n;
????while?(l?+?1?!=?u)?{
????????/*循環(huán)不變式a[l]
????????int?m?=?l?+?(u?-?l)?/?2;?//同（l+u）/?2
????????if?(t?>?a[m])
????????????l?=?m;
????????else
????????????u?=?m;
????}
????/*assert:?l+1=u?&&?a[l]
????int?p?=?u;
????if?(p>=n?||?a[p]!=t)
????????p?=?-1;
????return?p;
}

算法分析：設定兩個不存在的元素a[-1]和a[n]，使得a[-1] < t <= a[n]，但是我們并不會去訪問這兩個元素，因為(l+u)/2 > l=-1,?(l+u)/2 < u=n。循環(huán)不變式為la[l] && t<=a[u]?。循環(huán)退出時必然有l(wèi)+1=u, 而且a[l] < t <= a[u]。

循環(huán)退出后u的值為t可能出現(xiàn)的位置，其范圍為[0, n]，如果t在數(shù)組中，則第一個出現(xiàn)的位置p=u，如果不在，則設置p=-1返回。該算法的效率雖然解決了更為復雜的問題，但是其效率比初始版本的二分查找還要高，因為它在每次循環(huán)中只需要比較一次，前一程序則通常需要比較兩次。

舉個例子：對于數(shù)組a={1, 2, 3, 3, 5, 7, 8}，我們如果查找t=3，則可以得到p=u=2，如果查找t=4，a[3]=n, 比如t=9，則u=7，此時也是設置p=-1.特別注意的是，l=-1，u=n這兩個值不能寫成l=0，u=n-1。雖然這兩個值不會訪問到，但是如果改成后面的那樣，就會導致二分查找失敗，那樣就訪問不到第一個數(shù)字。如在a={1，2，3，4，5}中查找1，如果初始設置l=0，u=n-1，則會導致查找失敗。

擴展

如果要查找數(shù)字在數(shù)組中最后出現(xiàn)的位置呢？其實這跟上述算法是類似的，稍微改一下上面的算法就可以了，代碼如下：

/**
?*?二分查找最后一次出現(xiàn)位置
?*/
int?binarySearchLast(int?a[],?int?n,?int?t)
{
????int?l?=?-1,?u?=?n;
????while?(l?+?1?!=?u)?{
????????/*循環(huán)不變式,?a[l]?<=?t?
????????int?m?=?l?+?(u?-?l)?/?2;
????????if?(t?>=?a[m])
????????????l?=?m;
????????else
????????????u?=?m;
????}
????/*assert:?l+1?=?u?&&?a[l]?<=?t?
????int?p?=?l;
????if?(p<=-1?||?a[p]!=t)
????????p?=?-1;
????return?p;
}

當然還有一種方法可以將查詢數(shù)字第一次出現(xiàn)和最后一次出現(xiàn)的代碼寫在一個程序中，只需要對原始的二分查找稍微修改即可，代碼如下：

/**
?*?二分查找第一次和最后一次出現(xiàn)位置
?*/
int?binarySearchFirstAndLast(int?a[],?int?n,?int?t,?int?firstFlag)
{
????int?l?=?0;
????int?u?=?n?-?1;
????while(l?<=?u)?{
????????int?m?=?l?+?(u?-?l)?/?2;
????????if(a[m]?==?t)?{?//找到了，判斷是第一次出現(xiàn)還是最后一次出現(xiàn)
????????????if(firstFlag)?{?//查詢第一次出現(xiàn)的位置
????????????????if(m?!=?0?&&?a[m-1]?!=?t)
????????????????????return?m;
????????????????else?if(m?==?0)
????????????????????return?0;
????????????????else
????????????????????u?=?m?-?1;
????????????}?else?{???//查詢最后一次出現(xiàn)的位置
????????????????if(m?!=?n-1?&&?a[m+1]?!=?t)
????????????????????return?m;
????????????????else?if(m?==?n-1)
????????????????????return?n-1;
????????????????else
????????????????????l?=?m?+?1;
????????????}
????????}
????????else?if(a[m]?????????????l?=?m?+?1;
????????else
????????????u?=?m?-?1;
????}

????return?-1;
}

3 旋轉數(shù)組元素查找問題

題目

把一個有序數(shù)組最開始的若干個元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉。例如數(shù)組{3, 4, 5, 1, 2}為{1, 2, 3, 4, 5}的一個旋轉。現(xiàn)在給出旋轉后的數(shù)組和一個數(shù)，旋轉了多少位不知道，要求給出一個算法，算出給出的數(shù)在該數(shù)組中的下標，如果沒有找到這個數(shù)，則返回-1。要求查找次數(shù)不能超過n。

分析

由題目可以知道，旋轉后的數(shù)組雖然整體無序了，但是其前后兩部分是部分有序的。由此還是可以使用二分查找來解決該問題的。

解1：兩次二分查找

首先確定數(shù)組分割點，也就是說分割點兩邊的數(shù)組都有序。比如例子中的數(shù)組以位置2分割，前面部分{3,4,5}有序，后半部分{1,2}有序。然后對這兩部分分別使用二分查找即可。代碼如下：

/**
?*?旋轉數(shù)組查找-兩次二分查找
?*/
int?binarySearchRotateTwice(int?a[],?int?n,?int?t)
{
????int?p?=?findRotatePosition(a,?n);?//找到旋轉位置
????if?(p?==?-1)
????????return?binarySearchFirst(a,?n,?t);?//如果原數(shù)組有序，則直接二分查找即可

????int?left?=?binarySearchFirst(a,?p+1,?t);?//查找左半部分
????if?(left?!=?-1)
????????return?left;?//左半部分找到，則直接返回

????int?right?=?binarySearchFirst(a+p+1,?n-p-1,?t);?//左半部分沒有找到，則查找右半部分
????if?(right?==?-1)
????????return?-1;

????return?right+p+1;??//返回位置，注意要加上p+1
}

/**
?*?查找旋轉位置
?*/
int?findRotatePosition(int?a[],?int?n)
{
????int?i;
????for?(i?=?0;?i?-1;?i++)?{
????????if?(a[i+1]?????????????return?i;
????}
????return?-1;
}

解2：一次二分查找

二分查找算法有兩個關鍵點：1）數(shù)組有序；2）根據(jù)當前區(qū)間的中間元素與t的大小關系，確定下次二分查找在前半段區(qū)間還是后半段區(qū)間進行。

仔細分析該問題，可以發(fā)現(xiàn)，每次根據(jù) l 和 u 求出 m 后，m 左邊（[l, m]）和右邊（[m, u]）至少一個是有序的。a[m]分別與a[l]和a[u]比較，確定哪一段是有序的。

• 如果左邊是有序的，若?ta[l], 則 u=m-1；其他情況，l =m+1；

• 如果右邊是有序的，若?t> a[m] && t?則 l=m+1；其他情況，u =m-1；

代碼如下：

/**
?*?旋轉數(shù)組二分查找-一次二分查找
?*/
int?binarySearchRotateOnce(int?a[],?int?n,?int?t)
{
????int?l?=?0,?u?=?n-1;
????while?(l?<=?u)?{
????????int?m?=?l?+?(u-l)?/?2;
????????if?(t?==?a[m])
????????????return?m;
????????if?(a[m]?>=?a[l])?{?//數(shù)組左半有序
????????????if?(t?>=?a[l]?&&?t?????????????????u?=?m?-?1;
????????????else
????????????????l?=?m?+?1;
????????}?else?{???????//數(shù)組右半段有序
????????????if?(t?>?a[m]?&&?t?<=?a[u])
????????????????l?=?m?+?1;
????????????else
????????????????u?=?m?-?1;
????????}???
????}???
????return?-1;?
}




推薦閱讀：


【43期】盤點那些必問的數(shù)據(jù)結構算法題之二叉樹基礎


【42期】盤點那些必問的數(shù)據(jù)結構算法題之二叉堆


【41期】盤點那些必問的數(shù)據(jù)結構算法題之鏈表

2T技術資源大放送！包括但不限于：C/C++，Linux，Python，Java，PHP，人工智能，單片機，樹莓派，等等。在公眾號內回復「2048」，即可免費獲取！！

微信掃描二維碼，關注我的公眾號

朕已閱?