手帐 Blog

主题

15 · 二分变体 ​

目标：会做旋转数组搜索；建立「在答案上二分」的直觉。

为什么面试会考 ​

标准二分会了，面试官会换皮：

  • 数组「部分有序」（旋转）
  • 不是在下标上找，而是猜一个答案再验证（吃香蕉、平方根）

本质仍是：每次丢掉一半不可能的区间。

零基础概念 ​

旋转排序数组：[0,1,2,4,5,6,7] 旋转成 [4,5,6,7,0,1,2]。
任意 mid，左边或右边至少有一段是有序的——在有序那段里判断 target 是否落在里面。

答案二分：猜 speed = mid，若「能在 H 小时吃完」就尝试更小速度（r = mid），否则加大（l = mid + 1）。

JS 模板：答案二分 ​

js
function answerBinarySearch(lo, hi, check) {
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1)
    if (check(mid)) hi = mid // mid 可行，试更小
    else lo = mid + 1
  }
  return lo
}

check(mid)：返回「这个答案够不够好」。

精讲题 ​

LeetCode 33. 搜索旋转排序数组 ​

js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let l = 0
  let r = nums.length - 1
  while (l <= r) {
    const mid = l + ((r - l) >> 1)
    if (nums[mid] === target) return mid

    // 左半有序
    if (nums[l] <= nums[mid]) {
      if (nums[l] <= target && target < nums[mid]) r = mid - 1
      else l = mid + 1
    } else {
      // 右半有序
      if (nums[mid] < target && target <= nums[r]) l = mid + 1
      else r = mid - 1
    }
  }
  return -1
}

画图：先判断哪边有序，再看 target 在不在有序区间内。

LeetCode 875. 爱吃香蕉的珂珂 ​

速度 k 越小越慢。找最小的 k，使 H 小时内吃完。

js
/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function (piles, h) {
  let lo = 1
  let hi = Math.max(...piles)
  const canFinish = (k) => {
    let hours = 0
    for (const p of piles) {
      hours += Math.ceil(p / k)
    }
    return hours <= h
  }
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1)
    if (canFinish(mid)) hi = mid
    else lo = mid + 1
  }
  return lo
}

LeetCode 69. x 的平方根（巩固） ​

js
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  if (x < 2) return x
  let l = 1
  let r = x
  while (l <= r) {
    const mid = l + ((r - l) >> 1)
    const sq = mid * mid
    if (sq === x) return mid
    if (sq < x) l = mid + 1
    else r = mid - 1
  }
  return r // 向下取整
}

练习清单 ​

题提示
LeetCode 81. 搜索旋转排序数组 II有重复，相等时收缩边界
LeetCode 153. 寻找旋转排序数组中的最小值比 nums[r] 判断落在哪段
LeetCode 410. 分割数组的最大值（可选）答案二分 + 贪心验证
LeetCode 1011. 在 D 天内送达包裹的能力同 875 模板

今日验收 ​

  • [ ] 33 能说清「先判哪边有序」
  • [ ] 875 能写出 canFinish + 答案二分
  • [ ] 知道答案二分的 lo/hi 是答案范围，不是数组下标

若你以前见过 ​

竞赛里的「二分答案」就是这里的答案二分；前端面试常考到 875 / 1011 这一档。