算法 - Binary Search
笔者将在本文记录和学习 二分搜索 的解题笔记。
二分搜索是基础算法，但是并不简单。二分搜索真正的坑在于到底要给 mid +1 还是 -1 ，while 里到底用 <= 还是 <.
Ref: labuladong, liweiwei, etc.
Intuition
Binary search is an efficient array search algorithm. It works by narrowing down the search range by half each time. 是用来在一个有序数组中查找某一元素的算法。
前提
可以使用「二分查找」的前提是：问题告诉我们的 单调性。例如，数组是有序的。 有些问题虽然没有指出单调性，但是可以从题目中的描述得到可以 逐步缩小搜索区间 的条件，这些问题也可以使用「二分查找」来解决。
一定要找到某种单调性，才可以根据在区间 [left..right] 里猜的一个数 mid 的性质，决定:
mid是否有可能是解.- 下一 轮搜索是在
mid的左边还是在右边继续查找.
性质
时间复杂度
二分查找的最优时间复杂度为 O(1).
二分查找的平均时间复杂度和最坏时间复杂度均为 O(logn)。因为在二分搜索过程中，算法每次都把查询的区间减半，所以对于一个长度为 n 的数组，至多会进行 O(logn) 次查找.
空间复杂度
迭代版本的二分查找的空间复杂度为 O(1).
递归 (无尾调用消除) 版本的二分查找的空间复杂度为 O(logn).
while (left < right) 模板
此解法是笔者在一位打 ACM 的同学那里学习而来，也是他推荐的二分模板。同时该模板也是 liweiwei 所推荐的模板。惭愧的是，笔者对二分搜索迟迟没有理解透彻。故写下思路，以致巩固学习。
Explanation
假设目标值在闭区间 [left, right] 中， 每次将区间长度缩小一半，当 left = right 时，我们就找到了目标值。
while (left < right)表示当left与right重合的时候停止搜索，这样我们就不用思考返回left还是right.while里面只写两个 分支，即只有if和else，表示：非此即彼，把其中一种情况考虑好，不满足这种情况的区间就是上一个区间的反面区间。left,right是否+1:- 如果
mid在答案区间内，即mid. - 如果
mid不在答案区间内，即mid + 1.
- 如果
版本 1
当我们将区间 [left, right] 划分成 [left, mid] 和 [mid + 1, right] 时，其更新操作是 right = mid 或者 left = mid + 1; 计算 mid 时不需要加 1
在单调递增序列 A 中查找 >=x 的数当中最小的一个
// 目标元素可能存在在区间 [left..right]
while (left < right) {
int mid = left + (right - left) / 2;
if (a[mid] >= x) {
// 下一轮搜索区间 [left..mid]
right = mid;
} else {
// 下一轮搜索区间 [mid + 1..right]
left = mid + 1;
}
}
// 退出循环以后 left == right 成立
// 视情况判断 nums[left] 是否是我们要找的
版本 2
当我们将区间 [left, right] 划分成 [left, mid - 1] 和 [mid, right] 时，其更新操作是 right = mid - 1 或者 left = mid; 此时为了防止死循环，计算 mid 时需要加 1。
在单调递增序列 A 中查找 <=x 的数当中最大的一个
// 目标元素可能存在在区间 [left..right]
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (A[mid] <= x) {
// 下一轮搜索区间是 [mid..right]
left = mid;
} else {
// 下一轮搜索区间是 [left..mid - 1]
right = mid - 1;
}
}
// 退出循环以后 left == right 成立
// 视情况判断 nums[left] 是否是我们要找的
死循环
在搜索区间里只有两个元素的时候，mid = (left + right) / 2 取到的是中间位置靠左的元素的位置，mid = (left + right + 1) / 2 取到的是中间位置靠右的元素的位置。
使用流程
- 分析问题，左右半段哪个是可行区间，
mid归属哪半段 - 根据分析结果，选择两种配套形式之一:
right = mid,left = mid + 1,mid = (left + right) >> 1left = mid,right = mid - 1,mid = (left + right + 1) >> 1
- 二分终止条件是
left == right，该值就是答案所在位置
while (left <= right) 模板
本节模板学习参考自 Labuladong 东哥 探究几个最常用的二分查找场景：寻找一个数、寻找左侧边界、寻找右侧边界。而且，我们就是要深入细节，比如不等号是否应该带等号，
mid是否应该+1等等。分析这些细节的差异以及出现这些差异的原因，目标是能够灵活准确地写出正确的二分查找算法。
0. Template
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节
其中 ... 标记的部分，就是可能出现细节问题的地方，当你见到一个二分查找的代码时，首先注意这几个地方。后文用实例分析这些地方能有什么样的变化。
1. 基本二分搜索
这个场景是最简单的，可能也是大家最熟悉的，即搜索一个数，如果存在，返回其索引，否则返回 -1。
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
此算法有什么缺陷？
比如说给你有序数组 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。
2. 寻找左侧边界的二分搜索
统一写法模板的最终版本
int leftBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
} else if (nums[mid] == target) {
// 收缩右侧边界
right = mid - 1;
}
}
// 判断 target 是否存在于 nums 中
// 此时 target 比所有数都大，返回 -1
if (left == nums.length) return -1;
// 判断一下 nums[left] 是不是 target
return nums[left] == target ? left : -1;
}
为什么该算法能够搜索左侧边界？
答：关键在于对于 nums[mid] == target 这种情况的处理：
if (nums[mid] == target)
right = mid - 1;
可见，找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid-1] 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。
如何判断我们搜索到的结果？
对于这个数组，算法会返回索引 1
这个索引 1 的含义可以解读为 「nums中 小于 2 的元素有 1 个」
比如对于有序数组 nums = [2, 3, 5, 7], target = 1，算法会返回 0，含义是 nums中小于 1 的元素有 0 个。
再比如 nums = [2, 3, 5, 7], target = 8，算法会返回 4，含义是 nums中小于 8 的元素有 4 个。
综上可以看出，函数的返回值(即 left 变量的值)的取值区间是 [0, nums.length]，所以我们需要对 left 是否越界进行判断。
while (left <= right) {
//...
}
// 此时 target 比所有数都大，返回 -1
if (left == nums.length) return -1;
// 判断一下 nums[left] 是不是 target
return nums[left] == target ? left : -1;
3. 寻找右侧边界的二分搜索
统一写法模板的最终版本
int rightBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 这里改成收缩左侧边界即可
left = mid + 1;
}
}
// 最后改成返回 left - 1
if (left - 1 < 0) return -1;
return nums[left - 1] == target ? (left - 1) : -1;
}
为什么这个算法能够找到右侧边界？
答：类似地，我们在收缩左侧边界。当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的左边界 left，使得区间不断向右靠拢，达到锁定右侧边界的目的。
if (nums[mid] == target) {
left = mid + 1;
}
为什么最后返回 left - 1 而不像搜索左侧边界的函数，返回 left？
答：为什么要 -1，这是搜索右侧边界的一个特殊点，关键在锁定右边界时的这个条件判断：
// 增大 left，锁定右侧边界
if (nums[mid] == target) {
left = mid + 1;
// 这样想: mid = left - 1
}
如图，我们需要得到的答案是 index = 2.
因为我们对 left 的更新必须是 left = mid + 1，就是说 while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left-1] 可能是 target。
至于为什么 left 的更新必须是 left = mid + 1，是为了把 nums[mid] 排除出搜索区间。
如何判断我们搜索到的结果？
答：left 的取值范围是 [0, nums.length]，但由于我们最后返回的是 left - 1，所以 left 取值为 0 的时候会造成索引越界。我们需要判断越界。并且判断 nums[left - 1] == target.