Binary Search（二分查找）

题目 / Problem

中文： 给定一个按升序排列的整数数组 nums 和一个整数 target，请编写一个函数在 nums 中查找 target。如果目标值存在，返回它的下标；否则返回 -1。

算法的时间复杂度必须为 O(log n)。

English: Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search for target in nums. If target exists, return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

示例 / Examples

Example 1

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

解释 / Explanation:
9 存在于 nums 中，它的下标是 4。
9 exists in nums and its index is 4.

Example 2

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

解释 / Explanation:
2 不存在于 nums 中，因此返回 -1。
2 does not exist in nums, so return -1.

约束 / Constraints

1 <= nums.length <= 10⁴
-10⁴ < nums[i], target < 10⁴
nums 中的所有整数互不相同。
All the integers in nums are unique.
nums 按升序排列。
nums is sorted in ascending order.

解题思路：二分查找 / Approach: Binary Search

因为数组已经按升序排列，可以通过比较中间元素与目标值，每次排除一半的搜索范围。
Because the array is sorted in ascending order, comparing the middle element with the target lets us eliminate half of the remaining search range each time.

使用闭区间 [left, right] 表示当前仍可能包含目标值的范围：
Use the closed interval [left, right] to represent the range that may still contain the target:

初始化 left = 0、right = nums.length - 1。
Initialize left = 0 and right = nums.length - 1.
计算中间下标 mid。
Calculate the middle index mid.
如果 nums[mid] === target，返回 mid。
If nums[mid] === target, return mid.
如果 nums[mid] < target，目标值只可能在右半部分，令 left = mid + 1。
If nums[mid] < target, the target can only be in the right half, so set left = mid + 1.
如果 nums[mid] > target，目标值只可能在左半部分，令 right = mid - 1。
If nums[mid] > target, the target can only be in the left half, so set right = mid - 1.
当 left > right 时，搜索区间为空，返回 -1。
When left > right, the search interval is empty, so return -1.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function search(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] === target) {
      return mid;
    }

    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

使用 left + Math.floor((right - left) / 2) 计算中点，可以避免某些语言中 left + right 可能产生的整数溢出。
Calculating the midpoint with left + Math.floor((right - left) / 2) avoids the potential integer overflow of left + right in some languages.

执行过程 / Walkthrough

以 nums = [-1, 0, 3, 5, 9, 12]、target = 9 为例：
For nums = [-1, 0, 3, 5, 9, 12] and target = 9:

步骤 / Step	`left`	`right`	`mid`	`nums[mid]`	操作 / Action
1	0	5	2	3	`3 < 9`，令 `left = 3` / Set `left = 3`
2	3	5	4	9	找到目标，返回 `4` / Target found; return `4`

对于 target = 2：
For target = 2:

步骤 / Step	`left`	`right`	`mid`	`nums[mid]`	操作 / Action
1	0	5	2	3	`3 > 2`，令 `right = 1` / Set `right = 1`
2	0	1	0	-1	`-1 < 2`，令 `left = 1` / Set `left = 1`
3	1	1	1	0	`0 < 2`，令 `left = 2` / Set `left = 2`

此时 left = 2、right = 1，搜索区间为空，因此返回 -1。
Now left = 2 and right = 1, so the search interval is empty and the function returns -1.

为什么是 `O(log n)`？ / Why Is It `O(log n)`?

每次比较后，搜索范围都会缩小为原来的一半：
After each comparison, the search range is reduced by half:

n → n/2 → n/4 → n/8 → ... → 1

最多经过约 log₂ n 次比较，搜索范围就会缩小到一个元素，因此时间复杂度为 O(log n)。
After at most about log₂ n comparisons, the range is reduced to one element, giving a time complexity of O(log n).

复杂度 / Complexity

时间复杂度：O(log n)，每次循环排除一半的搜索范围。
Time: O(log n), because each iteration eliminates half of the search range.
空间复杂度：O(1)，只使用了常数个额外变量。
Space: O(1), because only a constant number of extra variables is used.

递归解法 / Recursive Approach

二分查找也可以递归实现：
Binary search can also be implemented recursively:

function searchRecursive(nums, target) {
  function binarySearch(left, right) {
    if (left > right) {
      return -1;
    }

    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] === target) {
      return mid;
    }

    if (nums[mid] < target) {
      return binarySearch(mid + 1, right);
    }

    return binarySearch(left, mid - 1);
  }

  return binarySearch(0, nums.length - 1);
}

时间复杂度 / Time: O(log n)
空间复杂度 / Space: O(log n)，递归调用会占用调用栈。
Recursive calls use the call stack.

迭代解法只需要 O(1) 额外空间，因此通常更合适。
The iterative solution is generally preferable because it uses only O(1) extra space.

易错点 / Common Pitfalls

使用闭区间 [left, right] 时，循环条件必须是 left <= right。
With the closed interval [left, right], the loop condition must be left <= right.
更新边界时必须排除已经比较过的 mid，即使用 mid + 1 或 mid - 1。
Boundary updates must exclude the already checked mid, using mid + 1 or mid - 1.
忘记移动边界可能导致无限循环。
Failing to move a boundary can cause an infinite loop.
找不到目标值时应返回 -1，不是插入位置。
Return -1 when the target is absent, not its possible insertion position.
二分查找依赖数组有序；无序数组不能直接使用该算法。
Binary search requires a sorted array and cannot be applied directly to an unsorted one.

Binary Search