编写一个函数，实现二分查找

推荐答案

// www.javascriptcn.com code example
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. 二分查找的基本思想

二分查找是一种高效的查找算法，适用于有序数组。它的基本思想是通过将数组分成两半，逐步缩小查找范围，直到找到目标值或确定目标值不存在。

2. 代码实现步骤

• 初始化指针：设置两个指针 left 和 right，分别指向数组的起始和末尾。
• 循环查找：在 left <= right 的条件下，计算中间索引 mid，并与目标值进行比较。
  • 如果 arr[mid] === target，则返回 mid，表示找到目标值。
  • 如果 arr[mid] < target，说明目标值在右半部分，将 left 更新为 mid + 1。
  • 如果 arr[mid] > target，说明目标值在左半部分，将 right 更新为 mid - 1。
• 未找到目标值：如果循环结束后仍未找到目标值，返回 -1。

3. 时间复杂度

二分查找的时间复杂度为 O(log n)，其中 n 是数组的长度。这是因为每次查找都将查找范围减半。

4. 注意事项

• 数组必须有序：二分查找的前提是数组必须是有序的，否则无法保证正确性。
• 边界条件：注意处理 left 和 right 的更新，避免死循环或越界。
• 返回值：如果找到目标值，返回其索引；否则返回 -1，表示未找到。