细拆二分法

这两周学到了二分相关，思想听起来颇为简单，实际写起来漏洞百出，如果是面向测试案例编程的话，经常胡乱+1-1，随机尝试>或者>=，拆了东墙补西墙，怎么堵都堵不明白。细节太多了，各种写法层出不穷，开区间的，闭区间的，左开右闭的，左闭右开的。找目标值的，找两端目标值位置的，找插入位置的，找最小的，找最大的，就是各种变了花样地找。所以还是一步步搞搞清楚，目前的总结只是从我刷到的六道题中总结的，但感觉万变不离其宗。所以来拿表格总结演示一下。

我的日常写法跟随大众写左闭右开，也就是说最后的答案基本是从left得到的。（虽然最后的退出条件是两者相等，但是为了统一还是用left。）

首先确定一些必要的条件：

1. 由于计算mid时，为了防止溢出，经常使用这一句：

1

mid=left+(right-left)/2;

所以，如果窗口长度为偶数，mid计算出来为偏向左边的索引。很符合左闭右开的规则。

举例：

left=3，right=6，mid=3+（6-3）/2=4.5=4。

left=0，right=1，mid=0+（1-0）/2=0.5=0。

想找的值比所有都大：

left=length-1, right=length, mid=length-1+(length-length+1)/2=length-1+0.5=length-1;

left=mid+1=length, 退出循环，进行最后的判断。

想找的值比所有都小：

left=0, right=1,mid=0+(1-0)/2=0.5=0

right=mid=0,此时left=right，退出循环，判断索引0是否为想要的值即可。

给的target不在里面怎么办

举个例子，此处具体数值只用small和big代表，防止陷入对数值的计算。

1 3 5 7 9 找6

left先到5，right还是9，然后right成为7，找不到的情况下，left和right肯定相邻，并且left为small，right为big。

为了细致表达，考虑完整的三种情况：

第一种：找不到的数的大小处于数组中间：

此时，left<right，还可以跑一次循环，left需要往右移动，变成：

此时，left=right，退出循环。最后，我们得到的left所指的这个数就是大于target的最小索引

第二种情况，target比所有数都小，right会不断往左移动，最后还是会和left相邻：

此时，由于mid比target大，right还需要往左移，变成：

此时，left=right，退出循环。left值不是我们想要的值，此时left就是大于target值的最小索引。

第三种情况，target比所有数都大，left会不断向右移动，最后和right相邻：

此时left还需要右移，得到：

此时left和right相等，退出循环。检查left的值，超出len-1，说明target比所有数都大。

至此，可以稍微总结一下找不到target的情况下，算出来的left：

• left就是大于target的最小索引，left左边绝对比target小。
• left直接跑出长度范围了，那么没别的意义，left-1即len-1即为最大值。

如果想求大于/小于target的最小/最大索引，但有重复target怎么办？

上面推导的情况，也就是target不出现/只出现一次时，小于/大于target的最小索引/最大索引其实根据推导的结论也能直接得到了。但是大部分的题目不长这么简单，它会出现很多重复的target，这时候就需要计算边界了。

一般的题目我们都不会知道target会不会存在于数组中。为了保险起见，下面会做完整的推理。

如果存在，并且有很多个，那么就需要计算边界了。首先计算左边界：

计算左边界的时候，如果得到了nums[mid]==target，也不能就此退出，需要继续寻找左边还有没有，这时候就需要让right向左挤压。

首先要想清楚一点，就是left只有在nums[mid]<target的时候才会移动。所以，nums[left]第一次和target相等后，就不会再动了，然后right步步紧逼，最后形成以下局面

再来一次循环，right再向左移动

此时，退出循环，left即为我们要找的最左边。

有很多题都会用到求最左侧的索引。比如2529这道题，找到比0小的，0有可能存在也有可能不存在。如果0存在，那么我们计算出left后，要检查left-1是否存在，如果存在，那么left左边都是比0小的，left-1就是小于0的最大索引。

如果0不存在，又回到了最初那个target不存在的情况，即left本身就为小于target值的最大索引。

-2，-1，3

那么如何求最右侧的索引呢？思路差不多，也就是让left向右步步紧逼。也要搞清楚一点，right的值只会在target<nums[mid]才会移动到mid上。如图，最后都会走向如此局面：

此时left还需要右移，得到下面：

此时left=right，而我们发现left所指的是x后面那个数，所以最后我们要返回left-1。

而其实，left即为大于target的最小索引。

那么如果target不存在呢？那我们又回到了最初的那种情况：left即为大于target的最小索引，小于left都比它小。

所以可以发现，如果想求大于target的值的多少，拿到left即可了，left的左边绝对都比tartget小。

那么搞明白这些，也就差不多了。

至于边际条件，搞清楚left的取值范围是[0,len]，注意一下为0时和为len时的情况即可。

回到题目总结：

先记住：

• lower_bound：第一个 ≥ target 的位置
• upper_bound：第一个 > target 的位置

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

思路：

• 第一个位置：lower_bound(target)
• 最后一个位置：upper_bound(target) - 1
• 特殊情况：检查元素是否存在

lc35 搜索插入位置：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

思路：

• 找第一个 ≥ target 的位置
• 解法：直接 lower_bound(target)

lc 744 寻找比目标字母大的最小字母：

给你一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters 里至少有两个不同的字符。

返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。

思路：

• 找第一个>target的字母，即用upper_bound。

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

给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。

• 换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。

注意：0 既不是正整数也不是负整数。

思路：

• 负数数量：第一个 ≥ 0 的位置 = lower_bound(0)
• 正数数量：总数 - 第一个 > 0 的位置 = n - upper_bound(0)
• 取两者最大值

lc 2300 咒语和药水的成功对数

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

思路：

• 对每个spell，找第一个 ≥ success/spell 的药水
• 解法：m - left_bound(success/spell)

lc 1385 两个数组间的距离值

给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。

「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。

思路

• 检查 [x-d, x+d] 区间是否为空
• 解法：找第一个 ≥ x-d 的位置，检查是否 > x+d

决策指南

注意数组越界和空数组的情况！

直接用STL

每次自己写寻找边界索引很麻烦，了解原理后直接上STL：

1
2
3
4
5
6
7
8
9

#include <algorithm>
using namespace std;

// 在 [first, last) 范围内查找
lower_bound(first, last, value);    // 第一个 ≥ value 的位置
upper_bound(first, last, value);    // 第一个 > value 的位置
equal_range(first, last, value);    // 返回 pair<lower_bound, upper_bound>
binary_search(first, last, value);  // 返回 bool，是否存在

基础用法：

1
2
3
4
5
6
7
8
9
10

vector<int> nums = {1, 3, 5, 7, 9};

// lower_bound: 第一个 ≥ 4 的位置
auto it1 = lower_bound(nums.begin(), nums.end(), 4);
// it1 指向 5，索引 = it1 - nums.begin() = 2

// upper_bound: 第一个 > 5 的位置  
auto it2 = upper_bound(nums.begin(), nums.end(), 5);
// it2 指向 7，索引 = 3