在一個「已經排好序」的陣列裡找目標,逐個比對顯得有點笨。二分搜尋(折半查找)的思路是:每次都拿中間那個元素跟目標比,比目標小就往右半邊找,比目標大就往左半邊找,每次都能砍掉一半的資料。n 個元素最多只需 log₂n 次比較——一千筆資料約十次就夠了。
/**
* 折半查找字符在数组中的位置(有序列表)
* @param array 被检索的数组
* @param x 要查找的字符
* @returns 字符在数组中的位置,没找到返回 -1
*/
function binarySearch(array, x){
var lowPoint = 1;
var higPoint = array.length;
var returnValue = -1;
var midPoint;
var found = false;
while ((lowPoint <= higPoint) && (!found)){
midPoint = Math.ceil((lowPoint + higPoint) / 2);
if(x > array[midPoint - 1]){
lowPoint = midPoint + 1;
} else if(x < array[midPoint - 1]){
higPoint = midPoint - 1;
} else {
found = true;
}
}
if(found){
returnValue = midPoint;
}
return returnValue;
}
var array2 = ['a','b','c','d','e','f','g'];
console.log(binarySearch(array2, 'c'));
lowPoint / higPoint 用的是「第幾個」的思維(從 1 開始數),而陣列下標從 0 開始,所以取用時一律寫成 array[midPoint - 1]。這是最常出錯的地方。ceil 往上取整可以確保 lowPoint 一定會前進,避免無窮迴圈。< 會漏掉只剩一個元素的情況。if (pos >= 0) 直接判斷,不必另外準備例外處理。原範例中最後的相等判斷寫成了 else if (x = array[midPoint - 1])——那是指派而非比較,會永遠為真。實務上請寫成 ===,並把常數放在左側(=== 加上左值寫法),可以讓這類筆誤在執行前就被發現。
另外要牢記前提:二分搜尋只能用在已排序的資料上。如果來源是未排序的陣列,先 sort() 再搜,或者改用 indexOf 之類的線性搜尋,取決於你查詢的頻率。