二分查找-模板二
# 模板二
模板二应用范围更广，应用于夹逼寻找满足条件的一个值，比如在一个有序数组中，寻找一个满足某条件（比如大于数组中的某一个值）的值，或在一个无重复数的数组中寻找到一个峰值（可能有多个峰值）。
适合解决区间内符合条件的某个值，而不是求解特定值，即使用夹逼法一步步缩小区间，最终缩小到一个点，就是答案（对于题目有确定答案的情况，如果不一定有答案则需要最后对该点进行判断）
示例：
在一个如上图所示的非递减区间内，其中A点与B点数值相同，通过模板二夹逼法可以找到A点和C点，但是找不到B点，具体可以见LC 34题分析。
# 模板代码
# 代码
// 官方模板，但这个模板并不常用，模板二的强大之处在于夹逼寻找结果
function binarySearch(nums, target) {
if (nums.length == 0) return -1;
// 左闭右开区间 [left, right)
// while循环内会少一次 left = right情况，需要在while循环后判断
let left = 0;
let right = nums.length;
while (left < right) {
// Prevent (left + right) overflow
// let mid = left + parseInt((right - left) / 2);
const mid = (left + right) >>> 1;
if (nums[mid] == target) return mid;
if (nums[mid] < target) {
left = mid + 1;
} else {
// 注意这里，保持 [left ,rigt) 左开右闭区间
right = mid;
}
}
// 循环结束条件 left == right，此时如果 left没有遍历到 nums.length，则需要判断 nums[left] == target的情况
// Post-processing:
// End Condition: left == right
if (left != nums.length && nums[left] == target) return left;
return -1;
}
// 夹逼模板，模板二代码更常用该模板
function binarySearch(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
// 循环直至区间左右端点相同
const mid = (left + right) >>> 1; // 防止计算时溢出
// nums[mid] 与某个值比较得出结果，比如调用外部函数、与nums[mid+1]、nums[right]等比较
if (compare(nums[mid])) {
right = mid; // mid可能为答案，需要留在答案区间，答案区间为 [left, mid]
} else {
left = mid + 1; // mid 肯定不是答案，需要从答案区间移除，移除后答案区间为 [mid+1, right]
}
}
// 此时有 left == right，区间缩为一个点，如果题目确定有一个答案，此区间点即为答案；如果没有一个确定的答案，需要判断
return left;
}
# 区分语法
- 初始条件：left = 0, right = length-1（并不是绝对，根据题目变化）
- 循环判断条件：left < right，这是核心，不断缩小区间，最后的那个点可能是答案
- 终止：left == right，如果题目确定有一个答案，left就是答案
- 向左查找：right = mid，此时mid可能是答案，需要留在答案区间
- 向右查找：left = mid+1，此时mid确定不是答案，需要从答案区间移除
注意：这里不可能是 left = mid; right = mid-1;，由于mid为向下去中，考虑[0,1]区间，mid = 0，如果此时 nums[mid] < target，mid会一直停留在left。即对于两个数的区间，mid == left，此时如果left不变化，则会陷入无限循环中。
# 例题
# LC 278. 第一个错误的版本 (opens new window)
Q：
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/first-bad-version 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
A：本题目是经典的模板二应用场景。题目一定有一个错误版本的答案，因此可用模板二夹逼去寻找答案。
/**
* Definition for isBadVersion()
*
* @param {integer} version number
* @return {boolean} whether the version is bad
* isBadVersion = function(version) {
* ...
* };
*/
/**
* @param {function} isBadVersion()
* @return {function}
*/
var solution = function (isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function (n) {
let left = 1;
let right = n;
// 肯定有一个正确答案，答案区间从 [left, right] 缩小为一个点 [left, left] 时，left 即为答案
while (left < right) {
const mid = (left + right) >>> 1;
if (isBadVersion(mid)) {
// mid 可能是答案，需要留在答案区间内
right = mid;
} else {
// mid 可以确定不是正确的答案，需要排除在答案区间外
left = mid + 1;
}
}
return left;
};
};
用一个例子来理解，如下图所示，共有6个版本，从第4个版本开始为错误的版本，现在就要通过二分法寻找出第4个版本。
- 第一步，mid = (1 + 6) / 2 = 3，第3个版本为正确的版本，即 mid = 3 肯定不是答案，因此 left = mid + 1，将 mid 排除答案区间，此时可能的答案区间为 [mid + 1, right]，即 [4, 6]
- 第二步，mid = (4 + 6 ) / 2 = 5，第5个版本为错误的版本，即 mid = 5 可能是答案，因此 right = mid，需要将mid留在答案区间，此时答案区间为 [left, mid]，即 [4, 5]。（注意，为什么说 mid = 5 可能是答案，因为 区间还有两个数，left 此时等于4，还没有验证过，不能将left排除，从图中也可以很明显的看出，mid = 5 不是正确答案）
- 第三步，mid = (4 + 5) / 2 = 4，第4个版本为错误的版本，即 mid = 4 可能是正确的答案，因此 right = mid = 4，需要将 mid 留在答案区间，此时答案区间为 [left, mid]，即 [4, 4]
- 第四补，此时答案区间为一个点，不满足 left < right 条件，因此这个点即为正确答案
综上可以发现，模板二是通过一步步缩小答案区间，夹逼寻找答案。需要注意的是：
- 为什么
left = mid + 1？因为此时 可以确定 mid 不是答案，需要将 mid 移除答案区间 - 为什么
right = mid？因为此时 mid可能是答案，需要留在答案区间
# LC 162. 寻找峰值 (opens new window)
Q：
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/find-peak-element 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
A：由于 nums[-1] = nums[n] = -∞，题目一定会有一个正确答案。采用爬坡法，即通过比较 mid 与 mid +1的值，一步步爬坡，最终找到一个坡顶元素就是答案
/**
* @param {number[]} nums
* @return {number}
*/
var findPeakElement = function (nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = (left + right) >>> 1;
// 爬坡法，通过比较 mid 与 mid+1 的值，一步步爬坡，最终爬到坡顶
if (nums[mid] < nums[mid + 1]) {
// 此时可以确定，mid 一定不是坡顶，因此把 mid 从答案区间排除
left = mid + 1;
} else {
// 此时 mid 可能是答案，需要把 mid 留在答案区间
right = mid;
}
}
// 任意一个坡顶即为答案，元素区间缩小至 [left, left]，
return left;
};
# LC 153. 寻找旋转排序数组中的最小值 (opens new window)
Q：
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
A：这题与33. 搜索旋转排序数组有点像，都为旋转排序数组，但本题求最小值，并不是明确的某个值的索引。先画出折线图，当mid在左或者右时，nums[left] 始终小于等于nums[mid]，没有变化；但是mid在左时，nums[mid] > nums[right]；当mid在右时 nums[mid] <= num[right]，由此产生了二段性。使用二分法模板二进行夹逼求值。
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function (nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = (left + right) >>> 1;
// 这里使用 < 或 <= 都可以
if (nums[mid] <= nums[right]) {
// mid 线在左边时，此时最小值一定在左侧
// 此时 mid 可能为答案，答案区间往左收敛，mid留在答案区间内
right = mid;
} else {
// mid 线在右边时，此时最小值一定在右侧
// 此时mid 肯定不是答案，答案区间往右收敛，将mid移除答案区间
left = mid + 1
}
}
return nums[left];
};
# LC 34. 在排序数组中查找元素的第一个和最后一个位置 (opens new window)
Q：
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
A：这一题虽然在力扣专题里放到了模板三，但其实用模板二更合适。先画一个折线图，用一个折线图来理解，这个折线图会更容易理解模板二的原理，即通过夹逼法使区间缩小到一个点，然后对该点判断是否是答案。
对于上图中的非递减数组，寻找A点和B点。使用模板二夹逼寻找可以找到A点和C点，但是找不到B点。
寻找A点：
// 非递减数组nums, 寻找target，寻找A点
{
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = (left + right) >>> 1;
// 区间不断缩小，如果 target存在，当区间缩小到一个点时 [left, left]，则 left 点一定是A点，这块可以用图中示例来一步步计算下方便理解
// 注意，这里是用的 < ，即 left 一步步逼近A点
if (nums[mid] < target) {
// 此时mid点一定不是 target，因此把 mid 从可能的答案区间中移除，移除后的答案区间为 [mid+1, right]
left = mid + 1;
} else {
// >= target
right = mid;
}
}
// 由于不一定存在target，因此需要对A点判断
if (nums[left] == target) {
start = left;
}
}
寻找C点：
// 非递减数组nums, 寻找target，寻找C点
{
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = (left + right) >>> 1;
// 注意这里，使用的是 <= ，则最终当区间缩小为一个点时， left 一定不是target (最后一位元素是target的情况除外，因此需要对这种情况做判断)，即 由于使用的是 <=，那么最终区间缩小到一个点时，left一定是 > target的（最后一位元素是target的特殊情况除外）
// 如果最后一位元素是target，则 nums[left] == target，在循环结束后单独对这种情况处理
if (nums[mid] <= target) {
left = mid + 1;
} else {
// > target
right = mid
}
}
if (nums[left] == target) {
// 数组的最后一个元素是target的情况
end = left;
} else {
// 寻找到的是C点，因此B点 = left - 1
end = left - 1;
}
}
最好是一步步把计算过程列出来，会更方便理解。
完整代码：
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var searchRange = function (nums, target) {
let start = -1;
let end = -1;
// 寻找A点
{
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = (left + right) >>> 1;
if (nums[mid] < target) {
left = mid + 1;
} else {
// >= target
right = mid;
}
}
if (nums[left] == target) {
start = left;
}
}
// 寻找B点，即先找到C点，然后 B = C - 1
{
// 如果A点不存在，即数组中不存在target，则B点也必然不存在
if (start != -1) {
// 寻找C点
let left = 0;
let right = nums.length - 1;
while (left < right) {
const mid = (left + right) >>> 1;
if (nums[mid] <= target) {
left = mid + 1;
} else {
// > target
right = mid
}
}
if (nums[left] == target) {
// 数组的最后一个元素是target的情况
end = left;
} else {
// 寻找的是最后一个target的下一个点，即C点，则 B = C - 1
end = left - 1;
}
}
}
return [start, end];
};
# LC 658. 找到 K 个最接近的元素 (opens new window)
Q：
给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x| 或者 |a - x| == |b - x| 且 a < b
提示：
1 <= k <= arr.length 1 <= arr.length <= 104 arr 按 升序 排列 -104 <= arr[i], x <= 104
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/find-k-closest-elements 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
A：这道题值得好好讲一讲，很多算法题都需要变通，即 很多算法题都遵循该公式：算法题 = 基础算法 + 题目变形。因此很多算法题都需要以下两步思考：
- 找出基础算法，即题目考察的核心算法，比如本题中，在数组中寻找符合条件的k个数，本质就是数组中寻找符合条件的某个数，一般来说，应用二分法模板二
- 找出题目变形，即题目在基础算法的基础上做了某些变化，需要对基础算法做改进才行，因此要先找出题目的变化点。例如本题中，条件为：更靠近x的k个数，即求对x差值的绝对值最小的k个数（左侧优先），那么我们可以把数组转变为对 x差值的绝对值数组。
结合一个例子来分析，对于数组[1,2,3,4,5,6,7,8,9,10]，寻找x=6的k个数。左图为原数组折线，右图为每个值与x=6求差值绝对值的数组折线
原数组折线图：
绝对差值数组折线图：
可以发现，折线变成了一个V型图（还有两种边界情况，一条斜向下的折线或一条斜向上的折线，分析方法是一样的），那么题目就可以转化为：对差值绝对值数组（右边V型图）中，求离x=6（左右相等时，左边优先)的k个原始点。
则可明显的看出，是求绝对差值数组V型图中最底部k个点（左边点优先），至此已经完成了两步分析：
- 基本算法，为二分法模板二
- 题目变形，是求绝对差值数组V型图中最底部k个点（左边点优先）
假设k=4，即求离x=6最近的4个点，则步骤就类似下面两张图，从第一张图逼近到第二张图，第二张图的 [A,B)个点就是离x=6最近的4个点
/**
* @param {number[]} arr
* @param {number} k
* @param {number} x
* @return {number[]}
*/
var findClosestElements = function (arr, k, x) {
const n = arr.length;
let left = 0;
// 这里需要保证 mid + k 不出界限，当mid = max_right时，也要满足mid + k < n，因此直接让右边界缩减k-1个数，
let right = n - k;
while (left < right) {
const mid = (left + right) >>> 1;
// 集合上面两张图理解，在绝对差值数组中，符合条件的k个点一定是 最左侧的点 <= 最右侧的点
// 左侧绝对差值点可以用 x - arr[mid] 表达，右侧绝对差值点可以用 arr[mid + k] - x 表达，注意，这里并没有用绝对差值，用差值表示出相对关系即可
if (x - arr[mid] > arr[mid + k] - x) {
left = mid + 1;
} else {
right = mid;
}
}
// 最后结果区间就为 [left, left+k) 这 k个点，即 left 最终到达符合条件的A点
return arr.slice(left, left + k);
};
注意点：
right = n - k的理解，由于需要保证 mid + k < n，则 mid < n - k，由于 while(left < right)，结合mid向下取中的特性，mid的最大值为 right -1，即 right - 1 < n - k，则 right < n - k -1，即right的最大值为 n - kx - arr[mid] > arr[mid + k] - x的理解，结合上面两个图的AB点理解
注：这个题目很经典，是模板二的进阶，需要好好理解。
# 小结
- 模板二非常强大，多用于在一个区间内寻找符合条件的某个数，即通过
while (left < right)使区间缩小到一个点[left, left]，对left这个点进行判断是否是答案。 - LC34题更适合用模板二，且用该题更容易理解模板二的原理。
- 通过模板二能直接找到A点和C点（对一个非递减区间，寻找A点和B点，且A == B）