前言
我們先來(lái)看下二分搜索維基解釋
- 在計(jì)算機(jī)科學(xué)中蛛蒙，折半搜索（英語(yǔ)：half-interval search）糙箍，也稱(chēng)二分查找算法（binary search）、二分搜索法牵祟、二分搜索深夯、二分探索，是一種在有序數(shù)組中查找某一特定元素的搜索算法诺苹。搜索過(guò)程從數(shù)組的中間元素開(kāi)始咕晋，如果中間元素正好是要查找的元素，則搜索過(guò)程結(jié)束收奔；如果某一特定元素大于或者小于中間元素掌呜，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開(kāi)始一樣從中間元素開(kāi)始比較坪哄。如果在某一步驟數(shù)組為空质蕉，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半翩肌。
我個(gè)人比較喜歡讀作“二分查找”模暗。
這里講點(diǎn)二分查找的概念準(zhǔn)備：
二分查找主要解決“在一堆數(shù)中找出指定值的位置”這類(lèi)問(wèn)題。
由此我們可以得出以下結(jié)論念祭，要想應(yīng)用二分查找兑宇，這一堆數(shù)必須滿(mǎn)足以下特征：
- 存儲(chǔ)在數(shù)組中
- 有序排列
所以如果是用鏈表存儲(chǔ)的，將無(wú)法應(yīng)用二分查找棒卷。（有的面試官會(huì)問(wèn)：二分查找用什么數(shù)據(jù)結(jié)構(gòu)顾孽？數(shù)組還是鏈表祝钢？）
至于“有序排列”是遞增還是遞減比规，數(shù)組中是否存在相同元素，這些都不重要拦英。不過(guò)一般情況蜒什，我們會(huì)希望數(shù)組是遞增排列奔害，且數(shù)組中的元素互不相同关拒。
如何做二分搜索
如果您認(rèn)真看了前言中附的二分查找基本概念骑丸，基本思路應(yīng)該有了发魄，而且我相信很多報(bào)班的小伙伴之前已經(jīng)聽(tīng)過(guò)甚至自己實(shí)現(xiàn)過(guò)。
這里先講個(gè)關(guān)于“二分查找”的有趣小故事
二分查找可以解決（預(yù)排序數(shù)組的查找）問(wèn)題：只要數(shù)組中包含T（即要查找的值）钞瀑，那么通過(guò)不斷縮小包含T的范圍沈撞，最終就可以找到它。一開(kāi)始雕什，范圍覆蓋整個(gè)數(shù)組缠俺。將數(shù)組的中間項(xiàng)與T進(jìn)行比較，可以排除一半元素贷岸，范圍縮小一半壹士。就這樣反復(fù)比較，反復(fù)縮小范圍偿警，最終就會(huì)在數(shù)組中找到T躏救，或者確定原以為T(mén)所在的范圍實(shí)際為空。對(duì)于包含N個(gè)元素的表螟蒸，整個(gè)查找過(guò)程大約要經(jīng)過(guò)log(2)N次比較盒使。
多數(shù)程序員都覺(jué)得只要理解了上面的描述，寫(xiě)出代碼就不難了七嫌；但事實(shí)并非如此忠怖。如果你不認(rèn)同這一點(diǎn)，最好的辦法就是放下書(shū)本抄瑟，自己動(dòng)手寫(xiě)一寫(xiě)凡泣。試試吧。
我在貝爾實(shí)驗(yàn)室和IBM的時(shí)候都出過(guò)這道考題皮假。那些專(zhuān)業(yè)的程序員有幾個(gè)小時(shí)的時(shí)間鞋拟，可以用他們選擇的語(yǔ)言把上面的描述寫(xiě)出來(lái)；寫(xiě)出高級(jí)偽代碼也可以惹资『馗伲考試結(jié)束后，差不多所有程序員都認(rèn)為自己寫(xiě)出了正確的程序褪测。于是猴誊，我們花了半個(gè)鐘頭來(lái)看他們編寫(xiě)的代碼經(jīng)過(guò)測(cè)試用例驗(yàn)證的結(jié)果。幾次課侮措，一百多人的結(jié)果相差無(wú)幾：90%的程序員寫(xiě)的程序中有bug（我并不認(rèn)為沒(méi)有bug的代碼就正確）懈叹。
我很驚訝：在足夠的時(shí)間內(nèi)，只有大約10%的專(zhuān)業(yè)程序員可以把這個(gè)小程序?qū)憣?duì)分扎。但寫(xiě)不對(duì)這個(gè)小程序的還不止這些人：高德納在《計(jì)算機(jī)程序設(shè)計(jì)的藝術(shù) 第3卷 排序和查找》第6.2.1節(jié)的“歷史與參考文獻(xiàn)”部分指出澄成，雖然早在1946年就有人將二分查找的方法公諸于世，但直到1962年才有人寫(xiě)出沒(méi)有bug的二分查找程序。
——喬恩·本特利墨状，《編程珠璣（第1版）》第35-36頁(yè)卫漫。
下面我們來(lái)動(dòng)手寫(xiě)一下看看這傳說(shuō)中干掉90%程序員的二分查找到底如何
//[參考鳴謝](http://blog.csdn.net/v_july_v/article/details/7093204)
int binarySearch(int *array, int left, int right, int value)
{
while (left<=right) //循環(huán)條件，適時(shí)而變
{
int middle = left + (right-left)/2; //使用“(left + right) / 2”可能會(huì)造成棧溢出
if (array[middle]>value)
{
right =middle-1; //right賦值肾砂，適時(shí)而變
}
else if(array[middle]<value)
{
left=middle+1;
}
else
return middle;
//可能會(huì)有讀者認(rèn)為剛開(kāi)始時(shí)就要判斷相等列赎，但畢竟數(shù)組中不相等的情況更多
//如果每次循環(huán)都判斷一下是否相等，將耗費(fèi)時(shí)間
}
return -1;
}
乍看之下也就區(qū)區(qū)十來(lái)行代碼镐确，但是其中有很多要容易犯錯(cuò)的細(xì)節(jié)粥谬，童鞋們需要特別注意注釋中提到的要點(diǎn)以及middle值的設(shè)定。
使用遞歸的二分搜索模板
簡(jiǎn)單粗暴辫塌，直接show code
int binarySearch(int *array, int left, int right, int value)
{
if (left > right) return -1;
int mid = left + (left + right)/2;
if (arrary[mid] == value) {
return mid;
} else if (array[mid]> value) {
return binarySearch(array, left, mid -1, value);
} else if (array[mid]< value) {
return binarySearch(array, mid+1, right, value);
}
}
A generic binary search template
汗漏策，看到這個(gè)標(biāo)題以為董老師要寫(xiě)C++模板，結(jié)果……
還是我自己來(lái)吧
//模板源碼
template<typename T>
bool binarySearch(vector<T> &array,T value)
{
int left = 0;
int right = array.size() -1;
while ( left <= right )
{
int middle = left + ( right - left ) /2;
if ( array[middle] == value )
{
return true;
}
else if ( array[middle] > value )
{
right = middle - 1;
}
else if ( array[middle] < value )
{
left = middle + 1;
}
}
return false;
}
//在vs下進(jìn)行簡(jiǎn)單測(cè)試臼氨，通過(guò)
//你可以改變數(shù)組的大小或者value的大小來(lái)進(jìn)行更多的測(cè)試
//如有更多問(wèn)題請(qǐng)聯(lián)系我email:alvinyeats@gmail.com
int _tmain(int argc, _TCHAR* argv[])
{
vector<int> array;
for(int i =0; i<20;i++)
array.push_back(i);
int value = 21;
bool status = binarySearch<int>(array, value);
cout << status << endl;
return 0;
}
Search Insert Position
leetcode原題地址
Given a sorted array and a target value, return the index
the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
沒(méi)啥可說(shuō)的掺喻，經(jīng)過(guò)上面的洗禮，做這個(gè)題應(yīng)該感覺(jué)很簡(jiǎn)單
示例代碼：
e32`123451
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int low = 0, high = nums.size()-1;
// Invariant: the desired index is between [low, high+1]
while (low <= high) {
int mid = low + (high-low)/2;
if (nums[mid] < target)
low = mid+1;
else
high = mid-1;
}
// (1) At this point, low > high. That is, low >= high+1
// (2) From the invariant, we know that the index is between [low, high+1], so low <= high+1. Follwing from (1), now we know low == high+1.
// (3) Following from (2), the index is between [low, high+1] = [low, low], which means that low is the desired index
// Therefore, we return low as the answer. You can also return high+1 as the result, since low == high+1
return low;
}
};
Search in Rotated Sorted Array
在輪轉(zhuǎn)后的有序數(shù)組上應(yīng)用二分查找
leetcode原題地址
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
該題要注意的地方是：判斷給定值到底屬于前面的區(qū)間{4,5,6,7}還是后面的區(qū)間{0,1,2}
這種數(shù)組并不是嚴(yán)格的遞增排列储矩，所以我們先比較M與L(也可以比較M與R感耙，道理是一樣的)，然后相對(duì)應(yīng)的來(lái)判斷要查找的key值是否位于[L,M]區(qū)間持隧，或是[M,R]區(qū)間即硼，從而確定下一步究竟是減小R還是增大M
int rotated_binary_search(int A[], int N, int key) {
int L = 0;
int R = N - 1;
while (L <= R) {
// Avoid overflow, same as M=(L+R)/2
int M = L + ((R - L) >> 1);
if (A[M] == key) return M;
// the bottom half is sorted
if (A[L] <= A[M]) {
if (A[L] <= key && key < A[M])
R = M - 1;
else
L = M + 1;
}
// the upper half is sorted
else {
if (A[M] < key && key <= A[R])
L = M + 1;
else
R = M - 1;
}
}
return -1;
}
擴(kuò)展：Search in Rotated Sorted Array II
有興趣的童鞋可以試下。
Find the Square Root
利用二分法找到一個(gè)數(shù)的平方根屡拨。
董老師的例程就很不錯(cuò)只酥，我就不自己寫(xiě)了
//函數(shù)功能
//輸入：待求平方根的數(shù)n
//輸出：誤差允許范圍內(nèi)n的平方根
float squareRoot(float n)
{
float x = n;
float y = 1;
float e = 0.000001; //e decides the accuracy level
while(x - y > e)
{
x = (x + y)/2;
y = n/x;
}
return x;
}
矩陣搜索
題目描述：Check if an element is in a M*N matrix, each row and column of which is sorted.
有題目可知，這個(gè)矩陣的每行每列都是排好序的呀狼，也就是說(shuō)每行每列是遞增（或遞減裂允，請(qǐng)自行分析）的。
我們簡(jiǎn)單構(gòu)造這樣一個(gè)矩陣：
1 5 10 20
2 6 11 30
7 9 12 40
8 15 31 41
利用這個(gè)矩陣的特性我們可以運(yùn)用二分查找的思想來(lái)簡(jiǎn)化這個(gè)問(wèn)題
解決方法：不用遞歸哥艇，從矩陣的右上角(x,y)開(kāi)始search（這樣有一個(gè)好處：(x,y)的左側(cè)所有點(diǎn)都小于matrxi[x][y], （x,y）的下側(cè)所有點(diǎn)都大于matrix[x][y]）绝编，在每個(gè)點(diǎn)都做這樣的判斷：
示例代碼：
bool isElementInMatrix(int **matrix, int M, int N, int target) {
int row = 0;
int column = N - 1;
while (row < M && column >= 0) {
if (matrix[row][column] == target) {
return true;
} else if (matrix[row][column] < target) {
row++;
} else {
column--;
}
}
return false;
}
Range Search
Given a sorted array of intergers with duplicates.Implement a function to get the start and end position of a given value.
有時(shí)我們并不是要尋找目標(biāo)值，而是尋找到“剛剛”大于給定值的值或者“剛剛”小于給定值的值貌踏。
用數(shù)學(xué)方式描述就是：在原集合中尋找包含目標(biāo)值區(qū)間的最小子集
void searchRangeHelper(int array[], int left, int right, int target, int &begin, int &end) {
if (left > right) {
return;
}
int mid = right - (right - left) / 2;
if (array[mid] == target) {
if (mid < begin || begin == -1) {
begin = mid;
}
if (mid > end) {
end = mid;
}
searchRangeHelper(array, left, mid - 1, target, begin, end);
searchRangeHelper(array, mid + 1, right, target, begin, end);
}
else if (array[mid] < target) {
searchRangeHelper(array, mid + 1, right, target, begin, end);
}
else {
searchRangeHelper(array, left, mid - 1, target, begin, end);
}
}
vector<int> searchRange(int A[], int n, int target) {
int begin = -1, end = -1;
searchRangeHelper(A, 0, n - 1, target, begin, end);
vector<int> ans;
ans.push_back(begin);
ans.push_back(end);
return ans;
}
