二分查找（binary search）

二分查找是一种适用于适用于有序数组的高时间效率和空间效率的搜索算法。

image-20260728155525341

对于闭区间[i, j]，二分查找的核心思想为两个步骤的循环：

  1. 计算中点索引 $m=\lfloor (i+j)/2 \rfloor$，其中$\lfloor \rfloor$表示向下取整操作，由于i + j 有可能溢出，一般使用 $\lfloor i+(j - i)/2 \rfloor$ 代替。
  2. 判断 $nums[m]$ 和 $target$ 的大小关系：
    1. $nums[m] < target$ ， $i = m + 1$ 。
    2. $nums[m] > target$ ， $j = m - 1$ 。
    3. $nums[m] = target$ ， return target 。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$；

int binarySearch(vector<int>& nums, int target) {
  int i = 0, j = nums.size() - 1;
  while ( i <= j) {
    int m = i + (j - i)/2;
    if (nums[m] < target) i = m + 1;
    else if (nums[m] > target) j = m - 1;
    else return m;
  }
  
  return -1;
}

image-20260728155603371