## 題目描述 給定一個有序的數組，查找某個數是否在數組中，請編程實現。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/04.01.md#分析與解法)分析與解法 一看到數組本身已經有序，我想你可能反應出了要用二分查找，畢竟二分查找的適用條件就是有序的。那什么是二分查找呢？ 二分查找可以解決（預排序數組的查找）問題：只要數組中包含T（即要查找的值），那么通過不斷縮小包含T的范圍，最終就可以找到它。其算法流程如下： * 一開始，范圍覆蓋整個數組。 * 將數組的中間項與T進行比較，如果T比數組的中間項要小，則到數組的前半部分繼續查找，反之，則到數組的后半部分繼續查找。 * 如此，每次查找可以排除一半元素，范圍縮小一半。就這樣反復比較，反復縮小范圍，最終就會在數組中找到T，或者確定原以為T所在的范圍實際為空。 對于包含N個元素的表，整個查找過程大約要經過log(2)N次比較。 此時，可能有不少讀者心里嘀咕，不就二分查找么，太簡單了。 然《編程珠璣》的作者Jon Bentley曾在貝爾實驗室做過一個實驗，即給一些專業的程序員幾個小時的時間，用任何一種語言編寫二分查找程序（寫出高級偽代碼也可以），結果參與編寫的一百多人中：90%的程序員寫的程序中有bug（我并不認為沒有bug的代碼就正確）。 也就是說：在足夠的時間內，只有大約10%的專業程序員可以把這個小程序寫對。但寫不對這個小程序的還不止這些人：而且高德納在《計算機程序設計的藝術 第3卷 排序和查找》第6.2.1節的“歷史與參考文獻”部分指出，雖然早在1946年就有人將二分查找的方法公諸于世，但直到1962年才有人寫出沒有bug的二分查找程序。 你能正確無誤的寫出二分查找代碼么？不妨一試，關閉所有網頁，窗口，打開記事本，或者編輯器，或者直接在本文評論下，不參考上面我寫的或其他任何人的程序，給自己十分鐘到N個小時不等的時間，立即編寫一個二分查找程序。 要準確實現二分查找，首先要把握下面幾個要點： * 關于right的賦值 * right = n-1 => while(left right = middle-1; * right = n => while(left right = middle; * middle的計算不能寫在while循環外，否則無法得到更新。 以下是一份參考實現： ~~~ int BinarySearch(int array[], int n, int value) { int left = 0; int right = n - 1; //如果這里是int right = n 的話，那么下面有兩處地方需要修改，以保證一一對應： //1、下面循環的條件則是while(left < right) //2、循環內當 array[middle] > value 的時候，right = mid while (left <= right) //循環條件，適時而變 { int middle = left + ((right - left) >> 1); //防止溢出，移位也更高效。同時，每次循環都需要更新。 if (array[middle] > value) { right = middle - 1; //right賦值，適時而變 } else if(array[middle] < value) { left = middle + 1; } else return middle; //可能會有讀者認為剛開始時就要判斷相等，但畢竟數組中不相等的情況更多 //如果每次循環都判斷一下是否相等，將耗費時間 } return -1; } ~~~ ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/04.01.md#總結)總結 編寫二分查找的程序時 * 如果令 `left <= right，則right = middle - 1; * 如果令left < right，則 right = middle;` 換言之，算法所操作的區間,是左閉右開區間,還是左閉右閉區間,這個區間,需要在循環初始化。且在循環體是否終止的判斷中,以及每次修改left, right區間值這三個地方保持一致,否則就可能出錯。