二分查找算法 四种题型六道题目总结，从此二分不迷路！
前言
二分查找在算法中一般有四类题目：
- 排序或通过排序后的数组，快速求某个值的下标
- 求某个值在数组中的左右端点
- 通过条件判断进行二分查找
- 局部有序的二分查找
- 33.搜索旋转排序数组（中等）
- 81.搜索旋转排序数组II（中等）
今天将这四类列举六道题，让大家一次看个够，从此二分不迷路！
35.搜索插入位置
难度：简单
题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，
返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例
示例 1:
输入: [1,3,5,6], 5
输出:
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
分析
手写二分解题
class Solution:
def searchInsert(self, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return left
api解题
class Solution:
def searchInsert(self, nums, target):
return bisect.bisect_left(nums, target)
34.在排序数组中查找元素的第一个和最后一个位置
难度：中等
题目
给定一个按照升序排列的整数数组 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]
分析
二分查找左右端点有一个小tips
- left = bisect_left(target)，如果left== length or nums[left] != target,
表示没有找到该数字，返回[-1, -1] - 在基于left的前提下，我们bisect_left(target + 1),
即可获取target下一个数字的插入点，然后right -1就是结果了。
解题
import bisect
class Solution:
def searchRange(self, nums, target):
left = bisect.bisect_left(nums,target)
if left == len(nums) or nums[left] != target:
return [-1,-1]
right = bisect.bisect_left(nums,target+1)
return [left,right - 1]
278.第一个错误的版本
难度：简单
题目：
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例：
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
分析
这是一道标准的，读题3分钟解题30秒题目。
其实只需要关注查找、尽可能少的次数这些关键字就可以判断出是一道二分查找的题目了。
题目中虚拟构建了 isBadVersion 方法用于判断结果是True or False。
所以，今天只能说是力扣庆祝端午快乐的一道放水送分题...
解题：
class Solution:
def firstBadVersion(self, n):
left = 1
right = n
while left < right:
mid = (left + right) // 2
if isBadVersion(mid):
right = mid
else:
left = mid + 1
return left
875.爱吃香蕉的珂珂
难度：中等
题目：
珂珂喜欢吃香蕉。这里有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
示例3：
输入: piles = [30,11,23,4,20], H = 6
输出: 23
分析：
由于1 <= piles.length <= 10^4, piles.length <= H <= 10^9所以肯定是二分查找没跑了。
下来看到最小时间，肯定是二分查找左边界。至于如何选择最大值，题目中描述：
“如果香蕉小于K根，他讲吃掉这堆的所有，并一小时内不会再吃更多香蕉”
所以我们最大值选择这个列表的max值即可。
解题：
class Solution:
def minEatingSpeed(self, piles, h):
def cost(k):
t = 0
for i in piles:
t += (i + k - 1) // k
return t
left, right = 1, max(piles)
while left < right:
mid = (left + right) // 2
ret = cost(mid)
if ret <= h:
right = mid
else:
left = mid + 1
return left
33.搜索旋转排序数组
难度：中等
题目
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，
使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，
则返回它的下标，否则返回 -1 。
提示：
- 1 <= nums.length <= 5000
- -10^4 <= nums[i] <= 10^4
- nums 中的每个值都 独一无二
- 题目数据保证 nums 在预先未知的某个下标上进行了旋转
- -10^4 <= target <= 10^4
进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？
示例
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
分析
第一次看这个题的时候，这能算中等？循环判断在不在不就完了。暴力通过，咦，效率还挺高？
沾沾自喜中看到了进阶要求，使用时间复杂度为O(log n)的方法完成...
O(log n)无疑二分才能实现，但是数组时无序的啊，我们先排序再二分？别逗，排序的时间复杂度就是O(n).
那么如何对局部有序的数组进行二分搜索呢？让我们以示例1为例：
nums = [4,5,6,7,0,1,2], target = 0
设置左右端点，left = 0 right = len(nums) -1。
有的小伙伴们要问了，你求length不是要一个一个加起来，复杂度不是O(n)么，错！
一定要记得Python的len()方法在获取数组长度时的时间复杂度是O(1).至于为啥篇幅原因百度吧...
mid = (0 + 6) // 2 == 3,此时nums[mid] == 7，下面开始判断。
- nums[mid]是否等于target，等于返回mid
- 关键来了，nums[mid]是否大于nums[left]
- 如果nums[left] <= nums[mid]
- nums[left] <= target < nums[mid],此时我们缩减right = mid - 1
- 否则，缩减left = mid + 1
- 如果nums[left] > nums[mid]
- nums[mid] < target <= nums[right],此时我们缩减left += 1
- 否则，缩减right = mid - 1
我们通过将局部有序的数据进行分场景考虑的情况，完成了二分的实现，这就是局部有序数组的二分操作方式。
- 如果nums[left] <= nums[mid]
暴力解法
class Solution:
def search(self, nums, target):
for i, num in enumerate(nums):
if target == num:
return i
return -1
解题
class Solution:
def search(self, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left += 1
else:
right -= 1
return -1
81.搜索旋转排序数组II
难度：中等
题目
已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，
使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。
如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
提示：
- 1 <= nums.length <= 5000
- -10^4 <= nums[i] <= 10^4
- 题目数据保证 nums 在预先未知的某个下标上进行了旋转
- -10^4 <= target <= 10^4
进阶：
- 这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
- 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
示例
示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
分析
先回答进阶问题，nums 可能包含重复元素，这会影响到程序的时间复杂度吗？
两种答案：
- 不会，我就是暴力return target in nums 管你有没有重复值呢，哈哈。
- 会，使用二分查找局部有序时，当nums[mid] == nums[left]时，
我无法知道他到底在翻转前的数组还是反转后的数组。只能left左移一位继续判断。
好了，做这道题之前，强烈建议先看看它的基础版题目，然后再来做这道题：
其实这道题，我们只需要根据33题的搜索改变一点判断就行，即当nums[left] == nums[mid] == nums[right],
此时我们不知道该怎么移动，那就left += 1 right += 1,再去判断即可。
解题
class Solution:
def search(self, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
if nums[left] == nums[mid] == nums[right]:
left += 1
right -= 1
continue
if nums[mid] <= nums[right]:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
else:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
return False
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
