二分查找
我们仍然从一个最基本的例题开始，随后讲解一下二分的扩展题型。
例题
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
思路
二分查找的基本思路有不少变种，我学习的是红蓝染色法，个人觉得这种方法是非常直观好理解的， 我最开始看的是b站灵茶山艾符的视频。
过去我们了解的二分查找的基本思想可能是从一个有序数组中不断取中值与target比较，相同则返回，不同则分类讨论。而在这里，我们把上述逻辑简化成了如果大于等于target，和小于target两种情况，于是我们分类讨论这两种情况，最终返回第一个大于等于target的数。
先简单说一下思路，左指针left指向最左边，右指针right指向最右边，如果中值小于target，说明需要左移left，反之亦然，下面是代码：
首先这里是闭区间
fun lower_bound(nums: IntArray, target: Int): Int{
// 我们最终返回第一个大于等于target的数
var left = 0
var right = nums.size - 1
// 显然，如果是闭区间的话，左右一开始指向的都是需要遍历（检查）的数
while (left <= right) {
// 我们思考一下，left和right处于什么状态时，说明所有数都已经被遍历，由于是闭区间，left > right 时，已完全遍历，while里反着写
val mid = left + (right - left) / 2
if (nums[mid] < target) {
left = mid + 1
// 由于是闭区间，这里实际的范围是[left, ... , right]
// 关于为什么这里要+1，如果 left = mid ，则数组实际上是[mid, ... , right]，而mid已经是小于target了，target如果存在于这个数组，则一定在[mid + 1, ... , right]中
} else {
right = mid - 1
}
}
return left
}
开区间
fun lower_bound(nums: IntArray, target: Int): Int{
var left = -1
var right = nums.size
// 指向不需要（无法）遍历的位置
while (left < right - 1) {
// left = right - 1时完成遍历
val mid = left + (right - left) / 2
if (nums[mid] < target) {
left = mid
// 由于是闭区间，这里实际上的范围是[left + 1, ..., right - 1]，所以不能left = mid + 1
} else {
right = mid
}
}
return left
}
至此，我们已经解决了如何从一个有序数组中找出第一个大于等于target的问题。
扩展：二分猜答案
接下来我们来看一种使用二分猜答案的题型。
例题
珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k（单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
示例 1：
输入：piles = [3,6,7,11], h = 8
输出：4
示例 2：
输入：piles = [30,11,23,4,20], h = 5
输出：30
思路
这道题乍一看和二分查找没什么关系，对吧？但仔细想想，我们要找的是"最小速度"，而这个速度显然是有范围的——最小是1，最大是最大那堆香蕉的数量（因为如果速度比这还大，那堆香蕉一小时就能吃完）。
我们是在一个有序的整数区间 [1, max(piles)] 中查找满足条件的最小值。这不就是二分查找的经典场景吗？
想想看，如果我们给定一个速度 k，能不能算出吃完所有香蕉需要多少小时？当然可以：
fun getHours(piles: IntArray, k: Int): Int {
var hours = 0
for (pile in piles) {
hours += (pile + k - 1) / k // 向上取整，等同于 ceil(pile / k)
}
return hours
}
现在我们有了判断函数 getHours(piles, k) <= h，就可以用二分查找来猜答案了：
fun minEatingSpeed(piles: IntArray, h: Int): Int {
var left = 1
var right = piles.maxOrNull()!! // 最大速度不会超过最大堆的香蕉数
while (left < right) {
val mid = left + (right - left) / 2
if (getHours(piles, mid) <= h) {
// 如果mid速度能在h小时内吃完，说明答案可能是mid或更小
right = mid
} else {
// mid速度太慢了，吃不完，需要加快速度
left = mid + 1
}
}
return left
}
为什么这样做是对的？
套路是这样的：二分猜答案的核心在于找到一个单调的判断函数。
如果速度 k 能在 h 小时内吃完，那么任何比 k 大的速度肯定也能吃完，对吧？这就是单调性——速度越快，所需时间越少。
于是我们就在这个单调的区间里二分查找，找到满足条件的最小值。
注意点
- 确定搜索范围：左边界通常是1，右边界要根据题目确定（比如最大堆、最大可能值等）
- 判断函数必须单调：这是二分猜答案的前提，如果不单调就无法使用
- 注意整数溢出：
left + (right - left) / 2比(left + right) / 2更安全