js实现二分查找

二分查找的基本原理

二分查找是一种在有序数组中查找特定元素的算法。通过将数组分成两半，比较中间元素与目标值，逐步缩小搜索范围，直到找到目标或确定不存在。

实现二分查找的步骤

初始化指针 定义两个指针left和right，分别指向数组的起始和末尾位置。

循环条件 当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;
}

// 示例用法
const sortedArray = [1, 3, 5, 7, 9];
console.log(binarySearch(sortedArray, 5)); // 输出: 2
console.log(binarySearch(sortedArray, 10)); // 输出: -1

边界条件与注意事项

数组必须有序 二分查找要求输入数组是有序的，否则结果不可预测。若数组无序，需先排序。

整数溢出问题 在计算mid时，left + right可能导致整数溢出。更安全的写法是使用left + Math.floor((right - left) / 2)。

重复元素处理 若数组中有重复元素，上述代码返回任意一个匹配的索引。如需返回第一个或最后一个匹配项，需进一步调整逻辑。

时间复杂度分析

二分查找的时间复杂度为O(log n)，其中n是数组长度。每次迭代都将搜索范围减半，效率远高于线性查找的O(n)。