二分查找有哪些常见变体？怎样找边界、在旋转数组里查找？

简答

最基本的二分是在有序数组里找某个数在不在。面试常考的是它的变体：数组里有重复的 8，要找第一个 8 和最后一个 8 的下标；或者数组被旋转过，比如 [4, 5, 6, 7, 0, 1, 2]，还要在 O(log n) 里找到目标。

找边界用两次二分。第一次找第一个大于等于目标的位置，这就是第一次出现的下标；第二次找第一个大于目标的位置，减 1 就是最后一次出现的下标。如果第一次找到的位置越界了，或者那里的值不等于目标，说明目标不存在，返回 [-1, -1]。

旋转数组整体不是有序的，但从中点切开，左右两半至少有一半是有序的。比较 nums[left] 和 nums[mid]，前者小于等于后者，说明左半边有序，否则右半边有序。目标落在有序那一半的范围里，就去那一半找，不然去另一半，这样每次仍然能排除一半。

写二分最容易错的是区间和循环条件不配套。选定一种写法，比如左闭右开 [left, right) 配 left < right，或者左闭右闭 [left, right] 配 left <= right，整段代码保持一致，空数组和只有一个元素的情况都要能跑通。

找第一个和最后一个位置

下面的 lowerBound 用左闭右开区间，返回第一个 >= target 的下标。把比较条件改成 <=，就得到第一个 > target 的下标。

function lowerBound(nums, target, inclusive = false) {
  let left = 0;
  let right = nums.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    // inclusive 为 true 时跳过所有等于 target 的值，找第一个大于 target 的位置。
    if (nums[mid] < target || (inclusive && nums[mid] === target)) left = mid + 1;
    else right = mid;
  }
  return left;
}

function searchRange(nums, target) {
  const first = lowerBound(nums, target);
  if (first === nums.length || nums[first] !== target) return [-1, -1];
  return [first, lowerBound(nums, target, true) - 1];
}

function searchRotated(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[left] <= nums[mid]) {
      // 左半边 [left, mid] 有序
      if (nums[left] <= target && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      // 右半边 [mid, right] 有序
      if (nums[mid] < target && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}

console.log(searchRange([5, 7, 7, 8, 8, 10], 8).join(',')); // 3,4
console.log(searchRange([5, 7, 7, 8, 8, 10], 6).join(',')); // -1,-1
console.log(searchRange([], 0).join(',')); // -1,-1
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0)); // 4
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 3)); // -1
console.log(searchRotated([1], 0)); // -1

这些输入都是 LeetCode 34 题和 33 题题面里的例子。

searchRange 里为什么第二次二分要减 1？第二次找到的是第一个大于 8 的位置，也就是 10 的下标 5，最后一个 8 就在它前面一格，下标 4。

为什么第一次二分之后要检查 nums[first] !== target？lowerBound 找的是第一个大于等于目标的位置，目标不存在时它也会返回一个位置。找 6 时，它返回 1，那里是 7，不等于 6，所以要返回 [-1, -1]。目标比所有数都大时，它返回数组长度，这时先判断 first === nums.length，避免读到数组外面。

旋转数组里怎样判断哪一半有序

[4, 5, 6, 7, 0, 1, 2] 是把 [0, 1, 2, 4, 5, 6, 7] 从 4 那里切开、前后调换得到的。数组里有一个“断点”，就是 7 到 0 那里。从中点切开，断点只可能在其中一半，另一半一定是有序的。

所以先看左半边：nums[left] <= nums[mid] 说明从 left 到 mid 没有断点，是有序的。这时判断目标在不在 nums[left] 到 nums[mid] 之间，在就去左边找，不在就去右边找。右半边有序时同理。

为什么是 <= 而不是 <？当 left === mid 时，左半边只有一个元素，它当然是有序的，这时两者相等，必须算作左半边有序。如果写成 <，就会误判成右半边有序。

要注意，这个写法依赖“元素互不相同”。LeetCode 33 题明确说了数组元素各不相同。如果有重复值，比如 [1, 0, 1, 1, 1]，nums[left]、nums[mid]、nums[right] 可能全部相等，判断不出哪一半有序，只能把 left 加 1 缩小一点，最坏情况退化成 O(n)。

两种区间写法怎么选

左闭右开 [left, right) 里，right 指向的位置不在搜索范围内，所以初始值是 nums.length，循环条件是 left < right，缩小右边界时写 right = mid。这种写法适合找边界，因为结果可能是 nums.length，表示插入到最后。

左闭右闭 [left, right] 里，right 也在搜索范围内，初始值是 nums.length - 1，循环条件是 left <= right，缩小时写 right = mid - 1。这种写法适合“找到就返回”的场景，比如上面的旋转数组。

中点写成 left + Math.floor((right - left) / 2)，原因见《二分查找怎样定位时间轴边界？为什么重复值和空数组容易写错？》。

常见追问

怎样找旋转数组里的最小值？

比较 nums[mid] 和 nums[right]。nums[mid] > nums[right] 说明断点在右半边，最小值在 mid 右侧，令 left = mid + 1；否则最小值在 mid 或它左侧，令 right = mid。循环到 left === right 时，那个位置就是最小值。

二分查找还能用在什么地方？

只要答案具有单调性就能用，不一定是在数组里找数。比如“最少需要多大的容量才能在 D 天内运完货物”，容量越大越容易满足，就可以对容量做二分，每次检查这个容量够不够。