js实现二分查找
二分查找的基本原理
二分查找是一种高效的搜索算法，适用于已排序的数组。通过每次将搜索范围减半，快速定位目标值的位置。时间复杂度为 O(log n)。
实现步骤
初始化指针
定义左指针 left 初始为 0，右指针 right 初始为数组长度减 1。
循环条件
当 left 小于等于 right 时，计算中间索引 mid，取 Math.floor((left + right) / 2)。
比较中间值
若中间值等于目标值，直接返回 mid。若中间值小于目标值，调整 left 为 mid + 1；否则调整 right 为 mid - 1。
未找到处理 循环结束后仍未找到目标值，返回 -1 或其他标识符。
代码示例
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}边界条件处理
空数组检查 在函数开始处添加对空数组的判断，直接返回 -1。
非数值处理 确保目标值和数组元素类型一致，避免隐式转换导致的错误。
递归实现
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
if (left > right) return -1;
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
return arr[mid] < target
? binarySearchRecursive(arr, target, mid + 1, right)
: binarySearchRecursive(arr, target, left, mid - 1);
}性能优化
位运算计算中点
使用 (left + right) >>> 1 替代 Math.floor，避免浮点数运算，提升速度。
提前终止 在特定场景下，如重复元素中寻找第一个或最后一个匹配项，可调整比较逻辑提前终止循环。
实际应用示例
const sortedArray = [1, 3, 5, 7, 9];
console.log(binarySearch(sortedArray, 5)); // 输出: 2
console.log(binarySearch(sortedArray, 10)); // 输出: -1注意事项
数组必须有序 二分查找要求输入数组严格升序或降序排列，否则结果不可预测。
大数处理
left + right 可能溢出，使用 left + (right - left) / 2 更安全。
