二分查找

来源：基础算法精讲 by 灵茶山艾府

视频精讲：二分查找

题目	代码	备注
34. 在排序数组中查找元素的第一个和最后一个位置	代码	三种写法
2529. 正整数和负整数的最大计数	代码	*课后作业
2300. 咒语和药水的成功对数	代码	*课后作业
1385. 两个数组间的距离值	代码	*课后作业
2080. 区间内查询数字的频率	代码	*课后作业
2563. 统计公平数对的数目	代码	*课后作业
875. 爱吃香蕉的珂珂	代码	*课后作业
2187. 完成旅途的最少时间	代码	*课后作业
275. H 指数 II	代码	*课后作业
2861. 最大合金数	代码	*课后作业
2439. 最小化数组中的最大值	代码	*课后作业
2517. 礼盒的最大甜蜜度	代码	*课后作业

例题

在排序数组中查找元素的第一个和最后一个位置

• 推荐开区间写法，循环不变量贯穿始终
• 初始化 l = -1, r = nums.length，(l, r) 表示开区间，两个端点明确不是答案
• 循环条件 l + 1 < r：当 l + 1 === r 时区间内无元素，停止循环
• nums[mid] >= target → 收缩 r = mid（第一个 >= target 的位置可能在 mid 或更左，包含 mid 本身）
• nums[mid] < target → 收缩 l = mid（mid 及左边都 < target，答案在右边）
• 循环结束后 l 和 r 相邻，r 就是第一个 >= target 的下标（即 lowerbound）
• 由于索引从 0 开始，偶数长度时 mid 视觉上偏左

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var lowerbound = function (nums, target) {
  let l = -1,
    r = nums.length;
  //要移动指针缩小范围，就要判断target跟中间值的大小
  //由于初始化两个开区间，那么循环条件就是r - l > 1？？不太懂对不对
  while (l + 1 < r) {
    const mid = Math.floor((l + r) / 2);
    //目标值在中间值左边，收缩右边指针，但是可能有连续的目标值，所以要有等于号
    if (nums[mid] >= target) r = mid;
    //相反
    else l = mid;
  }
  //循环结束之后，l跟r挨着，第一个target是r
  return r;
};
var searchRange = function (nums, target) {
  const start = lowerbound(nums, target);

  const end = lowerbound(nums, target + 0.5) - 1;
  //怎么，判断有没有取到正确答案？记住
  if (start === nums.length || nums[start] !== target) {
    return [-1, -1]; // nums 中没有 target
  }

  return [start, end];
};

时间复杂度：O(log n)，空间复杂度：O(1)

作业题

正整数和负整数的最大计数

略

咒语和药水的成功对数

• 排序 potions 后对每个 spell 二分查找，抓住有序特征
• 条件转化：spells[i] * potions[j] >= success → potions[j] >= ceil(success / spells[i])
• 为什么取 ceil：假如得到 3.4，用 3 就多了错误答案，4 刚刚好
• 踩坑：JS 箭头函数有花括号就要有 return

/**
 * @param {number[]} spells
 * @param {number[]} potions
 * @param {number} success
 * @return {number[]}
 */

var lowerbound = function (nums, target) {
    //开区间比较形象
    let l = -1, r = nums.length;
    //循环不变量：区间大于1，先找大于等于的
    while (l + 1 < r) {
        //注意，这里不必这样写，是cpp和java可能溢出，这里别忘记去除小数，下标必须是整数
        let mid = Math.floor(l + (r - l) / 2);

        if (nums[mid] >= target) r = mid;
        else l = mid;
    }
    return r;
}
var successfulPairs = function (spells, potions, success) {
    let m = spells.length, n = potions.length;
    let tmp,index, ans = [];
    //有花括号就要有return！！！
    potions.sort((a,b)=>a-b);
    // 要想应用二分查找，要抓住有序的特征，所以spells[m] * potions[n] >= 7;
    //变成了 potions[n] >= floor(7/ spells[m]),为什么取ceil，因为假如得到3.4,用3就多了错误答案，4刚刚好
    for(let i = 0; i < m; i++){
        tmp = Math.ceil(success/spells[i]);

        index = n - lowerbound(potions,tmp);
        // console.log(i,index,tmp)
        // ans = [...ans,index];
        ans.push(index);
    }
    return ans;
};

时间复杂度：O((m + n) log n)，空间复杂度：O(1)（不计排序空间）

两个数组间的距离值

• 绝对值条件 |arr1[i] - arr2[j]| > d 等价于 arr2 中没有元素落在 [x-d, x+d] 范围内
• 排序 arr2 后，用 lowerbound 找第一个 >= x - d 的元素，再检查它是否 <= x + d
• 分步判断：先定位再验证，注意二分的返回值是下标

var findTheDistanceValue = function (arr1, arr2, d) {
    let ans = 0;
    arr2.sort((a, b) => a - b);
    
    for (let x of arr1) {
        // 找第一个 >= x-d 的元素
        let idx = lowerbound(arr2, x - d);
        
        // 检查这个元素是否在 [x-d, x+d] 范围内
        // 如果 idx 在数组范围内，并且 arr2[idx] <= x+d，说明区间内有元素
        if (idx < arr2.length && arr2[idx] <= x + d) {
            // 存在元素在区间内，x不符合条件
            continue;
        } else {
            // 区间内没有元素，x符合条件
            ans++;
        }
    }
    
    return ans;

时间复杂度：O((m + n) log n)，空间复杂度：O(1)（不计排序空间）

区间内查询数字的频率

• 频率查询 → 用 Map 记录每个值出现的所有下标，Map 的值是数组
• 查询时对下标数组二分：找第一个 >= left 的位置和第一个 >= right + 1 的位置，差值即频率
• JS 类定义：构造函数 + 原型方法
• Map 常用 API：has（查键）、set(val, [])（插入数组为值）、get（取值）、数组的 push（追加元素）

// 构造函数（类似 C++ 的 RangeFreqQuery::RangeFreqQuery）
var RangeFreqQuery = function(arr) {
    // 在 JavaScript 中，this 指向新创建的对象
    // 相当于 C++ 的 this->indexMap
    this.indexMap = new Map();
    
    // 遍历数组，记录每个值的索引
    for (let i = 0; i < arr.length; i++) {
        const val = arr[i];
        if (!this.indexMap.has(val)) {
            this.indexMap.set(val, []);
        }
        this.indexMap.get(val).push(i);
    }
};



// 给原型添加 query 方法（类似 C++ 的成员函数）
RangeFreqQuery.prototype.query = function(left, right, value) {
    // 如果这个值从未出现过
    if (!this.indexMap.has(value)) {
        return 0;
    }
    
    const indices = this.indexMap.get(value);
    
    // 找第一个 >= left 的位置
    const leftIndex = lowerbound(indices, left);
    // 找第一个 > right 的位置（即第一个 >= right+1 的位置）
    const rightIndex = lowerbound(indices, right + 1);
    
    // 范围内索引的个数
    return rightIndex - leftIndex;
};

时间复杂度：构造 O(n)，查询 O(log n)；空间复杂度：O(n)

统计公平数对的数目

• 排序后对每个 nums[i]，在 [i+1, n-1] 范围内二分查找满足 lower <= nums[i] + nums[j] <= upper 的 j
• 改造 lowerbound，多传入一个 start 参数保证不重复计数（j > i）
• 踩坑：传 i+1 而非 i，否则 x 与 [x, y] 匹配会把自己也算进去，应该是 x 与 [x+1, y]
• 虽然最终还是没搞出来，但已经接近得很了——读题 → 模拟样例 → 想办法用代码实现

/**
 * @param {number[]} nums
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */

//处理特殊情况，全是0
var countFairPairs = function (nums, lower, upper) {
    const n = nums.length;
    let ans = 0;

    nums.sort((a, b) => a - b);

    for (let i = 0; i < n; i++) {
        let tmpl = lower - nums[i], tmpr = upper - nums[i];
        //为什么要i+1，因为是当前值与后面的区间值匹配，如果是i，就比如,x与[x,y]匹配了，把自己也算了进去，应该是x与[x+1,y]
        if(i < n - 1) ans += lowerbound(nums, tmpr+1,i+1) - lowerbound(nums, tmpl,i+1);
        console.log('ans',ans)
    }
    return ans;

};


//多传入一个start参数保证不重复计数
var lowerbound = function (nums, target,start) {
    //开区间比较形象
    let l = start - 1, r = nums.length;
    //循环不变量：区间大于1，先找大于等于的
    while (l + 1 < r) {
        //注意，这里不必这样写，是cpp和java可能溢出，这里别忘记去除小数，下标必须是整数
        let mid = Math.floor(l + (r - l) / 2);

        if (nums[mid] >= target) r = mid;
        else l = mid;
    }
    return r;
}

时间复杂度：O(n log n)，空间复杂度：O(1)（不计排序空间）

爱吃香蕉的珂珂

• 二分答案：不是在数组下标上二分，而是在答案范围 [1, max(piles)] 上二分
• 开区间的真正含义：left = 0（明确不可行，速度不能为 0）、right = max(piles)（明确可行，n 堆最多 n 小时吃完，题目保证 n ≤ h）
• 合法条件 sum <= h（总时间不超限）→ 尝试更小速度 r = mid
• 不合法 sum > h（超时）→ 需要提速 l = mid

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */

//二分查找模版的变体而已，就是改了一下判断条件
//找最小，就是刚好大于等于
var minEatingSpeed = function (piles, h) {
    piles.sort((a, b) => a - b);
    let l = 0, r = Math.max(...piles);
    while (l + 1 < r) {
        let sum = 0;
        //求和，尝试找k，容易发现k的范围就是数组最小值和最大值之间
        let mid = Math.floor((l + r) / 2);

        for (const x of piles) {
            sum += Math.ceil(x / mid);
        }
        // console.log(mid, sum)
        //往左的时候，条件为,当前花的时间要大于规定时间，答案可能在。。。。。。哦不对，sum大于h，说明超时了，那要提升速度，mid要变大，所以要往右；
        // if (sum >= h ) r = mid;
        //所以花的时间小于规定时间（合法），那就尝试找更小的速度
        if (sum <= h) r = mid;
        ///不合法，花的时间sum大于h，那自然要提速度
        else l = mid;
    }

    return r;
};

时间复杂度：O(n log max(piles))，空间复杂度：O(1)

完成旅途的最少时间

• 二分答案：猜一个时间 mid，计算所有车在该时间内能完成的总旅程数
• 左边界 l = min(time) - 1（最快的车至少需要 1 个单位时间），右边界 r = max(time) * totalTrips
• sum >= totalTrips → 时间够用，尝试更少 r = mid；否则 l = mid

//最少时间，也就是找到t，得到的旅途数刚好大于等于target；
//二分猜测，猜4答案是t，计算旅程数
//注意，越快的车走的旅程数越多
var minimumTime = function (time, totalTrips) {

    //最少多少时间？按照速度最快的时间基准来
    //最多多少时间？就算速度最慢的，这个时间由次数乘以最大的单位时间
    let mint = Math.min(...time);
    //
    let l = mint - 1, r = Math.max(...time)*totalTrips;

    while (l + 1 < r) {
        let mid = Math.floor((l + r) / 2);
        let sum = 0;
        for(let x of time){
            sum += Math.floor(mid/x)
        }
        if (sum >= totalTrips) r = mid;
        else l = mid;
    }
    return r;
};

时间复杂度：O(n log(max(time) × totalTrips))，空间复杂度：O(1)

H 指数 II

• 已排序数组，找第一个满足 citations[mid] >= n - mid 的位置
• 考虑极端情况：最少 0 篇论文引用 0 次，最多 n 篇论文至少引用了 n 次
• 开区间 l = -1, r = n，答案为 n - r

var hIndex = function (citations) {
    //考虑极端情况；最少1篇论文引用0次，最多n篇论文至少引用了n次；中间靠后h篇论文引用h次

    let n = citations.length;
    let l = - 1, r = n;

    while (l + 1 < r) {
        let mid = Math.floor((l + r) / 2);
        if (citations[mid] >= n - mid) r = mid;
        else l = mid;
    }
    return n - r;

};

时间复杂度：O(log n)，空间复杂度：O(1)

最大合金数

不做了

最小化数组中的最大值

不做了

礼盒的最大甜蜜度

• 最大化最小值 → 典型二分答案特征，排序后再尝试
• 贪心验证：对于猜测的甜蜜度 d，从最小价格开始，每次选第一个与上一个差 >= d 的糖果
• 如果能选出 >= k 个，说明 d 可行（left = mid）；否则 d 太大（right = mid）
• 题目要返回的最大甜蜜度是一个差值，但验证时不是做差而是贪心逐个验证，思维转换在这和二分的结合点上
• 需要一个 pre 变量记录上一个选中的糖果价格

模拟过程

价格数组 price = [1, 2, 5, 8, 13, 21]，k = 3：

确定猜答案的范围：

• 左边界 left = 0（最小间距）
• 右边界 right = 20（最大价格 21 - 最小价格 1）

猜 d = 10：

1. 先选 1
2. 找 >= 1 + 10 = 11 → 选 13
3. 找 >= 13 + 10 = 23 → 找不到

只选出 2 个 < k = 3，太大了，去左半边 [0, 9]。

猜 d = 7：

1. 先选 1
2. 找 >= 1 + 7 = 8 → 选 8
3. 找 >= 8 + 7 = 15 → 选 21

选出 3 个 >= k，可行！甜蜜度为 7。（选出 (1, 8, 21)）

var maximumTastiness = function(price, k) {
    function f(d) {
        let cnt = 1, pre = price[0]; // 先选一个价格最小的糖果
        for (const p of price) {
            if (p - pre >= d) { // 可以选 p
                cnt++;
                pre = p;
            }
        }
        return cnt;
    }

    price.sort((a, b) => a - b);
    let left = 0;
    let right = Math.floor((price[price.length - 1] - price[0]) / (k - 1)) + 1;
    while (left + 1 < right) { // 开区间不为空
        // 循环不变量：
        // f(left) >= k
        // f(right) < k
        const mid = Math.floor((left + right) / 2);
        if (f(mid) >= k) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return left; // 最大的满足 f(left) >= k 的数
};

时间复杂度：O(n log((max - min) / (k - 1)))，空间复杂度：O(1)（不计排序空间）

为什么 f(d) >= k 就够了？

如果贪心选出了 m 个糖果（m >= k），那么这 m 个糖果中任取 k 个，它们之间的最小差一定 >= d：

• 贪心选出的 m 个糖果，每相邻两个的差都 >= d
• 从中任取 k 个，跳过了中间的一些糖果，差只会更大
• 所以这 k 个糖果也一定满足任意差 >= d

例子（d=5）：
选 1 (prev=1)
选 8 (8-1=7≥5) ✓
选 13 (13-8=5≥5) ✓
结果：差值 [7,5]，最小差=5 ≥ d ✅

贪心策略为什么能得到最多？

命题：对于排序后的价格数组，每次都选第一个满足"与上一个差 >= d"的糖果，能得到最多的糖果数。

基础情况 — 第一个选最小的总是最优：

假设最优解第一个选的是 price[i] (i > 0)，把它替换成 price[0]：

• price[0] <= price[i]
• 起点更小，后面的糖果更容易满足差价条件
• 替换后至少不会选得更少

归纳步骤 — 每次选第一个可行的是最优：

设第一个满足条件的糖果价格为 x，假设最优解选了价格为 y 的（y >= x）：

比较两种选择：
┌─────────────────────────────────────────┐
│ 贪心选 x                                 │
│ 后面可选的糖果：所有 ≥ x+d 的糖果         │
├─────────────────────────────────────────┤
│ 最优解选 y                                │
│ 后面可选的糖果：所有 ≥ y+d 的糖果         │
└─────────────────────────────────────────┘

因为 x ≤ y，所以 {糖果 ≥ y+d} ⊆ {糖果 ≥ x+d}
也就是说，选 x 后面的可选集合 ≥ 选 y 后面的可选集合

反例验证：

价格：[1, 3, 4, 6, 9]，d = 3

贪心：选 1 → 选 4 → 选 9 → [1,4,9] 共 3 个
跳过 4 选 6：选 1 → 选 6 → 选 9 → [1,6,9] 也是 3 个
跳过更多：选 1 → 选 9 → [1,9] 只有 2 个 ❌

跳过一个可行选择不会增加后续机会：
- 跳过的数 x 能满足条件
- 后面选的 y ≥ x
- 起点变大了，可选集合变小了

类比：活动选择问题

这很像经典的"活动选择"问题：

• 每个糖果看作一个"活动"，"开始时间"是价格
• 条件 p - pre >= d 相当于两个活动之间必须有至少 d 的间隔
• 贪心策略：每次选第一个满足间隔条件的（即当前可选中最小的）就是最优

附录

开闭区间概述

区间定义决定了边界值的含义：

• 闭区间：left 和 right 都是当前可能包含答案的范围
• 左闭右开：right 是第一个不满足条件的位置（或超出范围）
• 开区间：left 是最后一个 < target 的位置，right 是第一个 >= target 的位置

循环条件随之变化：必须保证区间内至少有一个待检查的元素。

更新规则必须维持循环不变量：这是最核心的。只要你维护好不变量，最终答案就会落在预期的边界上。

mid 落在 target 索引的位置是否受影响？不，Math.floor((left+right)/2) 在所有实现中都是一样的，只是 left 和 right 的值不同，导致 mid 的取值序列可能不同。但最终搜索到的目标位置是相同的。mid 只是一个探针，帮助我们缩小范围。

为什么开区间写法可能更直观？

• 左边界的左边所有元素 < target（且左边界本身 < target）
• 右边界的右边所有元素 >= target（且右边界本身 >= target）
• 每次比较 mid 后，根据结果将 mid 赋给左或右边界，区间始终保持开区间，且不变量自动维持
• 循环结束时，左右边界相邻，此时右边界就是第一个 >= target 的位置
• 不需要 ±1 操作，不容易出现边界错误，因此许多算法竞赛选手偏爱这种风格

为什么用 floor 而不是 ceil

核心原因：保持区间不变量的正确性。

假设数组 [1, 3, 5, 7, 9]，l = -1, r = 5：

mid = Math.floor((l + r) / 2) = Math.floor(4 / 2) = 2
// 得到中间偏左的位置，没问题

关键场景：当 l 和 r 相邻时（l + 1 = r）：

• (l + r) / 2 = l + 0.5
• floor 得到 l
• ceil 得到 r

如果用 ceil：

while (l + 1 < r) {
    mid = Math.ceil((l + r) / 2);  // 当 l+1=r 时，mid = r
    
    if (nums[mid] >= target) {
        r = mid;  // r 不变（还是 r）
    } else {
        l = mid;  // l 变成 r
    }
    // 区间没缩小！可能死循环
}

用 floor 就安全：

while (l + 1 < r) {
    mid = Math.floor((l + r) / 2);  // 当 l+1=r 时，mid = l
    
    if (nums[mid] >= target) {
        r = mid;  // r 变成 l，区间缩小
    } else {
        l = mid;  // l 变成 l（不变？）
    }
    // 检查：如果 nums[l] < target，l 不变，但 r 会变
    // 无论如何，区间一定会缩小
}

偶数长度视觉化：

数组长度 6（偶数）：[10, 20, 30, 40, 50, 60]
下标：0   1   2   3   4   5

中间有两个值：下标 2(30) 和 3(40)
用 floor: (0+5)/2 = 2.5 → floor = 2 ✓ 取左边的中间值
用 ceil:  (0+5)/2 = 2.5 → ceil  = 3 ✗ 取右边的中间值

二分查找的标准实现都选 floor（左边），因为代码简单、避免边界死循环、符合编程直觉。

JS 数组方法

let arr = [1, 2, 3];

arr.push(4);           // 末尾添加 → [1, 2, 3, 4]
arr.pop();             // 末尾删除 → [1, 2, 3]
arr.unshift(0);        // 开头添加 → [0, 1, 2, 3]
arr.shift();           // 开头删除 → [1, 2, 3]

方法	是否创建新数组	性能	返回值
push	否（修改原数组）	高	新数组长度
展开运算符 [...ans, count]	是（创建新数组）	较低	新数组

循环中用 push 性能更好，不会每次创建新数组。

上下取整转换

⌈a/b⌉ = ⌊(a-1)/b⌋ + 1（当 a, b 为正整数时）

为什么要做这个变换？ 避免浮点数精度问题，用整数运算代替浮点数运算。

// 直接上取整（刷题常用，99% 情况够用）
sum += Math.ceil(p / mid);

// 公式转换（避免浮点数精度问题，工程场景更稳）
sum += Math.floor((p - 1) / mid) + 1;

验证：

• a=7, b=3: ⌈7/3⌉ = 3, ⌊6/3⌋+1 = 2+1 = 3 ✓
• a=6, b=3: ⌈6/3⌉ = 2, ⌊5/3⌋+1 = 1+1 = 2 ✓
• a=5, b=3: ⌈5/3⌉ = 2, ⌊4/3⌋+1 = 1+1 = 2 ✓

求和公式展开：把每个 ⌊(p-1)/k⌋+1 加起来 = sum(⌊(p-1)/k⌋) + n ≤ h，这是数学上的简化写法，对实际写代码没有太大帮助，但有助于理解数学本质。

结论：刷题直接用 Math.ceil(p/mid) 完全没问题，不影响二分查找的核心思想。

三种区间写法详解（以珂珂吃香蕉为例）

闭区间 [left, right]

function minEatingSpeed(piles, h) {
    let left = 1;      // 最小可能速度
    let right = Math.max(...piles);  // 最大可能速度
    
    while (left <= right) {  // [left, right] 不为空
        let mid = Math.floor((left + right) / 2);
        
        if (canFinish(piles, mid, h)) {
            right = mid - 1;  // mid 已经可行，试试更慢的
        } else {
            left = mid + 1;   // mid 不可行，需要更快的
        }
    }
    return left;  // 循环结束时，left 是第一个可行的
}

• 初始：left=1（可行？未知），right=max（可行？未知）
• 循环条件：left <= right 表示区间还有元素
• 移动规则：排除 mid 后，区间缩小为 [left, mid-1] 或 [mid+1, right]
• 结束时：left > right，left 就是答案

左闭右开 [left, right)

function minEatingSpeed(piles, h) {
    let left = 1;      // 最小可能速度
    let right = Math.max(...piles) + 1;  // 注意这里 +1
    
    while (left < right) {  // [left, right) 不为空
        let mid = Math.floor((left + right) / 2);
        
        if (canFinish(piles, mid, h)) {
            right = mid;     // mid 可行，把右边界拉过来
        } else {
            left = mid + 1;  // mid 不可行，排除后往右
        }
    }
    return left;  // 循环结束时，left == right 就是答案
}

• 初始：left=1，right=max+1（right 本身不在区间内）
• 循环条件：left < right 表示区间还有元素
• 移动规则：right=mid 表示新的右边界（不包含 mid），left=mid+1 表示排除 mid
• 结束时：left == right，这个值就是答案

开区间 (left, right)

function minEatingSpeed(piles, h) {
    let left = 0;      // 肯定不可行的
    let right = Math.max(...piles);  // 肯定可行的
    
    while (left + 1 < right) {  // (left, right) 不为空
        let mid = Math.floor((left + right) / 2);
        
        if (canFinish(piles, mid, h)) {
            right = mid;     // mid 可行，更新右边界
        } else {
            left = mid;      // mid 不可行，更新左边界
        }
    }
    return right;  // 循环结束时，right 是第一个可行的
}

• 初始：left=0（明确不可行），right=max（明确可行）
• 循环条件：left + 1 < right 表示中间还有元素
• 移动规则：直接 left=mid 或 right=mid，不 +1/-1
• 结束时：left 和 right 相邻，right 就是答案

对比表

方面	闭区间 [L,R]	左闭右开 [L,R)	开区间 (L,R)
左指针初始	最小可能值	最小可能值	明确不可行的值
右指针初始	最大可能值	最大可能值+1	明确可行的值
循环条件	L ≤ R	L < R	L + 1 < R
可行时移动	R = mid - 1	R = mid	R = mid
不可行时移动	L = mid + 1	L = mid + 1	L = mid
返回答案	L	L	R

开区间写法最容易理解：左右边界有明确含义（不可行 vs 可行），移动指针不用想 ±1，循环结束时答案直接是 right。