前提:**數組必須有序(升序)**。
每次取中間索引 mid = Math.floor((low+high)/2),比較 arr[mid] 與目標值:
midhigh = mid - 1low = mid + 1時間複雜度 O(log n),空間 O(1)(迭代)或 O(log n)(遞歸棧)。
function binarySearchRecursive(arr, target, low, high) {
if (low > high) return -1;
var mid = Math.floor((low + high) / 2);
if (arr[mid] === target) return mid;
return arr[mid] > target
? binarySearchRecursive(arr, target, low, mid - 1)
: binarySearchRecursive(arr, target, mid + 1, high);
}
// 調用
var arr = [3,5,6,7,9,12,15];
console.log(binarySearchRecursive(arr, 15, 0, arr.length-1)); // 6
function binarySearchIterative(arr, target) {
var low = 0, high = arr.length - 1;
while (low <= high) {
var mid = Math.floor((low + high) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] > target) high = mid - 1;
else low = mid + 1;
}
return -1;
}
function lowerBound(arr, target) { // 第一個 >= target
var low = 0, high = arr.length;
while (low < high) {
var mid = (low + high) >> 1;
if (arr[mid] < target) low = mid + 1;
else high = mid;
}
return low;
}
function upperBound(arr, target) { // 第一個 > target
var low = 0, high = arr.length;
while (low < high) {
var mid = (low + high) >> 1;
if (arr[mid] <= target) low = mid + 1;
else high = mid;
}
return low;
}
// 目標值出現範圍 [lowerBound, upperBound-1]
function searchRotated(arr, target) {
var low = 0, high = arr.length - 1;
while (low <= high) {
var mid = (low + high) >> 1;
if (arr[mid] === target) return mid;
if (arr[low] <= arr[mid]) { // 左半有序
if (arr[low] <= target && target < arr[mid]) high = mid - 1;
else low = mid + 1;
} else { // 右半有序
if (arr[mid] < target && target <= arr[high]) low = mid + 1;
else high = mid - 1;
}
}
return -1;
}
>> 0 或 | 0 快速取整(位運算比 Math.floor 快)(low+high)/2 溢出(JS 數字安全整數 2⁵³-1,實際極少溢出,但習慣用 low + ((high-low)>>1))compareFnO(n log n) 再查不如線性 O(n)