前言

做这个题的时候 H-Index，二分搜索算法写来写去都写不对，经过阅读大量文献，和好多技术文章，简单了解了一下二分搜索的写法。

我们不妨假设，下面讨论的二分搜索是在一个以自然数（包含 0）作为下标的单调递增（单调递减同理，比较的时候换个方向就可以了）数组中，寻找与给定目标值相等，或者最大的小于等于（或者大于等于）目标值的数（也可以说此时目标值就成为了一个下（上）界，或者说左侧（右侧）的边界）。

二分搜索中，我们通常会定义左边界 $left$，右边界 $right$，每次取左右边界的均值 $left + \text{floor}((right - left) / 2)$，指向的数组元素与目标值 $target$ 比较，然后移动左右边界，最后在 $left < right$ 或者 $left \leq right$ 的时候终止循环，然后返回目标值的下标。

个人认为二分搜索可能遇到的问题在于：每次搜索边界如何移动，怎么判断终止循环，结果需要怎么取。自己在写二分搜索的时候，感觉对于终止循环的表达式怎么去写还是挺迷惑的，是 $left < right$ 还是 $left \leq right$，不同的写法也会影响到边界移动的方式以及如何返回结果下标。

与目标值相等

1. 在 $[left, right)$ 中搜索

在数组 $nums$ 上面搜索，最初可行区间为 $[left, right)$。这种想法是很自然的，毕竟我们会把左边界设置为 $num$ 第一位下标 0，右边界为数组长度 $nums.length$，但是 $nums[nums.length]$ 超出了边界。

此时循环退出条件为：

1. 找到了 $target$ 返回结果下标；
2. 找不到，返回 -1，也就是说这个时候 $[left, right)$ 空了，于是有 $left < right$ 时退出循环；

ts
function binarySearch(nums: number[], left: number, right: number, target: number): number {
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] < target) {
      left = mid + 1
    } else if (nums[mid] === target) {
      return mid
    } else {
      right = mid
    }
  }
  return -1
}

描述一下每次迭代都发生了什么：

1. 一开始可行域是 $[left, right)$；
2. 如果 $nums[mid] < target$，就是说 $[left, mid]$ 都不满足，因此 $left = mid + 1$ 看 $[mid + 1, right)$ 的情况；
3. 如果 $nums[mid] < target$，$[mid, right)$ 都不满足，因此 $right = mid$ 看 $[left, mid)$ 的情况；
4. 如果找到了 $nums[mid] = target$ 就返回结果，最后找不到返回 -1;

2. 在 $[left, right]$ 中搜索

那现在要在 $[left,right]$ 闭区间进行搜索，需要怎么处理呢，很简单，把上面的右边界 +1 就行了，也可以采用退出循环条件为 $left \leq right$ 的写法，因为是闭区间，没有找到结果时终止循环肯定得让区间为空，在 $left = right$ 时区间里面还有东西，还得再迭代一步缩小一下。

ts
function binarySearch(nums: number[], left: number, right: number, target: number): number {
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] < target) {
      left = mid + 1
    } else if (nums[mid] === target) {
      return mid
    } else {
      right = mid - 1
    }
  }
  return -1
}

我们又来描述一下每次迭代都发生了什么：

1. 一开始可行域是 $[left, right]$；
2. 如果 $nums[mid] < target$，$[left, mid]$ 都不满足，因此 $left = mid + 1$ 看 $[mid + 1, right]$ 的情况；
3. 如果 $nums[mid] < target$，$[mid, right]$ 都不满足，因此 $right = mid - 1$ 看 $[left, mid - 1]$ 的情况；
4. 如果找到了 $nums[mid] = target$ 就返回结果，最后找不到返回 -1;

大于等于目标值的最小值

此时，我们需要的索引最靠左的，大于等于目标值 $target$ 的数组元素。算法和与目标值相等的情况类似，关键在于，目标值不一定在数组中，或者有多个目标值，于是需要考虑 $nums[mid] = target$ 时边界如何移动。

1. 在 $[left, right)$ 中搜索

ts
function binarySearch(nums: number[], left: number, right: number, target: number): number {
  if (target > nums[right - 1]) {
    return -1
  }
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] < target) {
      left = mid + 1
    } else if (nums[mid] > target) {
      right = mid
    } else {
      right = mid
    }
  }
  return left
}

每次迭代都发生了什么：

1. 如果 $target$ 比所有数都大返回 -1；
2. 一开始可行域是 $[left, right)$；
3. 如果 $nums[mid] \not= target$
   3.1. 如果 $nums[mid] < target$，就是说 $[left, mid]$ 都小于 $target$，因此 $left = mid + 1$ 看 $[mid + 1, right)$ 的情况；
   3.2. 如果 $nums[mid] < target$，就是说 $[mid, right)$ 都大于 $target$，因此 $right = mid$ 看 $[left, mid)$ 的情况；
4. 如果数组元素都不等于 $target$，循环结束时，$left = right$，返回最不小于目标值的下标 $left$（$right$ 也行，下同）
5. 如果找到了 $nums[mid] = target$，$(mid, right)$ 都大于等于 $target$，但是 $mid$ 比 $(mid, right)$ 都更“左”，是更优的选项，可以让 $right = mid$；
   5.1. 如果 $[left, mid)$ 中没有等于 $target$ 的数，则 $left$ 向右移动直至 $left = right$，循环结束，返回大于等于目标值的最小值的下标 $left$;
   5.2. 如果 $[left, mid)$ 中有等于 $target$ 的数，则在迭代过程中 $right$ 最终向右移动直至 $[left, mid)$ 为空或者其中数组元素都小于 $target$ ，然后见 5.1;

2. 在 $[left, right]$ 中搜索

我们当然也可以把右边界 + 1，但是可以有另一种写法

ts
function binarySearch(nums: number[], left: number, right: number, target: number): number {
  if (target > nums[right]) {
    return -1
  }
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] < target) {
      left = mid + 1
    } else if (nums[mid] > target) {
      right = mid - 1
    } else {
      right = mid - 1
    }
  }
  return left
}

类似地：

1. 如果 $target$ 比所有数都大返回 -1；
2. 一开始可行域是 $[left, right]$；
3. 如果 $nums[mid] \not= target$；
   3.1. 如果 $nums[mid] > target$，就是说 $[left, mid]$ 都小于 $target$，因此 $left = mid + 1$ 看 $[mid + 1, right]$ 的情况；
   3.2. 如果 $nums[mid] < target$，就是说 $[mid, right]$ 都大于 $target$，因此 $right = mid - 1$ 看 $[left, mid - 1]$ 的情况；
4. 如果数组元素都不等于 $target$，循环结束时，$left = right + 1$，$nums[right] < target < nums[right + 1$，返回最不小于目标值的下标 $left$；
5. 如果找到了 $nums[mid] = target$，$[mid, right]$ 都大于等于 $target$，但是 $mid$ 比 $[mid, right]$ 都更“左”，是更优的选项，可以让 $right = mid - 1$ （即使 $nums[mid - 1] < target$也可以获得正确结果，参考第 4 步）；
   5.1. 如果 $[left, mid)$ 中没有等于 $target$ 的数，则 $left$ 向右移动直至 $left = right + 1$，循环结束，返回下标 $left$;
   5.2. 如果 $[left, mid)$ 中有等于 $target$ 的数，则在迭代过程中 $right$ 最终向右移动直至 $[left, mid)$ 为空或者其中数组元素都小于 $target$ ，然后见 5.1;

小于等于目标值的最大值

需要搜索小于等于目标值的下标最后的元素：

1. 在 $[left, right)$ 中搜索

ts
function binarySearch(nums: number[], left: number, right: number, target: number): number {
  if (target < nums[0]) {
    return -1
  }
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] < target) {
      left = mid + 1
    } else if (nums[mid] > target) {
      right = mid
    } else {
      left = mid + 1
    }
  }
  return left - 1
}

为什么结果是 $left - 1$ ?

因为当$nums[mid] \leq target$ 时，$mid = mid + 1$，那结束时，$nums[left]$ 就成为第一个大于 $target$ 的元素了。

2. 在 $[left, right]$ 中搜索

ts
function binarySearch(nums: number[], left: number, right: number, target: number): number {
  if (target < nums[0]) {
    return -1
  }
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] < target) {
      left = mid + 1
    } else if (nums[mid] > target) {
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  return left - 1
}

总结

类型	初始可行域	结束条件	小于目标值	等于目标值	大于目标值	成功返回	失败条件
与目标值相等	$[left, right)$	left < right	left = mid + 1	return mid	right = mid	mid	目标值不在数组中
	$[left, right]$	left <= right	left = mid + 1	return mid	right = mid - 1	mid	目标值不在数组中
大于等于目标值的最小值	$[left, right)$	left < right	left = mid + 1	right = mid	right = mid	left	目标值大于数组任何元素
	$[left, right]$	left <= right	left = mid + 1	right = mid - 1	right = mid - 1	left	目标值大于数组任何元素
小于等于目标值的最大值	$[left, right)$	left < right	left = mid + 1	left = mid + 1	right = mid	left - 1	目标值小于数组任何元素
	$[left, right]$	left <= right	left = mid + 1	left = mid + 1	right = mid - 1	left - 1	目标值小于数组任何元素