二分查找又叫折半查找,優點很突出:比較次數少、查找速度快、平均性能好。缺點同樣明顯:要求待查數據必須有序,且插入刪除成本高。因此它最適合「不常變動、但查詢頻繁」的有序集合。
假設元素按升序排列。先把中間位置的元素與目標比較:相等則查找成功;不等則利用中間位置把表分成前後兩個子表——中間值大於目標就往前半區找,反之往後半區找。重複這一過程,直到找到目標,或子表不存在為止。
每一次比較都能排除一半數據,所以時間複雜度是 O(log n)。100 萬條有序數據,最多只需約 20 次比較。
var Arr = [3, 5, 6, 7, 9, 12, 15];
function binary(find, arr, low, high) {
if (low <= high) {
// 先判斷兩端,能減少後續循環次數
if (arr[low] == find) return low;
if (arr[high] == find) return high;
var mid = Math.ceil((high + low) / 2);
if (arr[mid] == find) {
return mid;
} else if (arr[mid] > find) {
return binary(find, arr, low, mid - 1); // 縮小右界
} else {
return binary(find, arr, mid + 1, high); // 抬高左界
}
}
return -1; // 未找到
}
binary(15, Arr, 0, Arr.length - 1); // 6
遞歸版本的關鍵是每次調用都要把 low 或 high 往中間收攏一格,否則會陷入死循環。同時必須有 low <= high 這個終止條件,它標誌著搜索區間已經為空。
若改寫成迭代版本,只需用 while 循環包住上述邏輯,能省掉函數調用開銷,在數據量大時更受青睞:
function binaryIter(find, arr) {
var low = 0, high = arr.length - 1;
while (low <= high) {
var mid = Math.floor((low + high) / 2);
if (arr[mid] === find) return mid;
if (arr[mid] > find) { high = mid - 1; }
else { low = mid + 1; }
}
return -1;
}
還有一個實務細節:當 low + high 可能溢出時,改用 low + (high - low) / 2 更安全。在 JavaScript 中由於 Number 是雙精度浮點,一般不必擔心,但在其他語言裡這是一個經典面試陷阱。