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

推荐答案

-- -------------------- ---- -------
-------- ----------------- ------- -
    --- ---- - --
    --- ----- - ---------- - --

    ----- ----- -- ------ -
        ----- --- - ---------------- - ------ - ---

        -- --------- --- ------- -
            ------ ---- -- ----------
        - ---- -- --------- - ------- -
            ---- - --- - -- -- --------
        - ---- -
            ----- - --- - -- -- --------
        -
    -

    ------ --- -- ------
-

本题详细解读

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，表示未找到。