实现 js 二分查找
参考答案
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid = (left + right) >> 1; // 或 left + ((right-left)>>1) 防溢出
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
要点:
- 前提是有序数组;
- 边界用
<=,退出时 left > right; >>1可避免浮点,但大数需注意 32 位限制;推荐Math.floor((l + r) / 2);- 找左右边界(第一个 ≥ target /最后一个 ≤)用变体:命中后继续收缩;
- 复杂度 O(log n)。