不想看的可以直接拉到最后看模板
只要问题可以转化为【在有一定规律的区间内查找一个target】，就可以使用本文的二分查找模板
区间的左闭右开
数学上区间边界有【开闭】之分。我们通过开闭的组合可以形成4种区间的表达方式。以序列0，1，2，3为例：
- 双闭 0 <= x <= 3
- 双开 -1 < x < 4
- 左闭右开 0 <= x < 4
- 左开右闭 -1 < x <= 3
【双闭】和【左闭右开】是最符合人类自然逻辑的2种区间表示方法
而大神Dijkstra早在1982年就对这4种区间表示方法的优劣进行了论述，详见链接https://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF，结论是左闭右开是表示区间最友好最出色的方式，原因如下：
- 1.上下界之差直接表示元素的个数
- 2.在表示两个相邻子序列时相当方便和简洁：一个子序列的上界就是另一个子序列的下界
- 3.当上界等于下界时即可表示空集，不会出现上界小于下界的情况。而双闭在表示空集时必然需要上界小于下界，比较难看，如0 <= x <= -1
因为原因2和3的存在，左闭右开在表示子序列以及子序列的边界关系上具有优势。左闭右开的优势在于能够高效完成序列切片并且保证edge case的正确
因此，左闭右开表示法在编程中处理线性序列问题时对边界情况非常友好。事实上，编程中出现了左闭右开的大量应用，如python的range()函数，slice操作等等
从左闭右开到二分查找
二分查找的思想或许很容易用文字描述，但要真正编程实现，在细节处理上（尤其一些边界问题）往往会出现各种各样的bug
我们可能习惯于使用双闭方式去描述一个区间，现在我们要基于以上对左闭右开方式的优势分析，使用左闭右开实现二分查找。我们会发现，这异常简洁。以下是基于左闭右开的二分查找插入位置【下界】的基本模板：
# 给定一个非降序数组和target，返回在数组中插入target的最小下标
class Solution:
def binarySearchInsert(self, nums: List[int], low, high, target: int) -> int:
while low < high:
mid = low + ( high - low ) // 2
if nums[mid] < target:
# 当【mid小于target】时，target必在mid的右侧，将low提高至mid+1
low = mid + 1
else:
# 当【mid大于或者等于target】时，target必在mid的左侧或mid位置，将high移动至mid
high = mid
# 跳出循环，low == high，定位待插入位置
return low
左闭右开的一些小优点
- 1.代码分支更少。将普通二分查找(实际上是3分，> = & < 3种情况)转为真二分查找
- 2.边界条件更加简洁。无需在mid分割的左右区间边界上过多地讨论+-1，只需讨论一个分支
- 3.阅读和编写友好。当查找区间只包含一个元素时，low和high不会重合
注意：
- 1.取中点mid = (low + high) // 2虽然在python中不会产生溢出，因为python可以表示无限大的数，但是在c++/java等语言中则可能面临low + high的数值溢出问题。为增强程序的鲁棒性，使用mid = low + (high - low) // 2 会更优
- 2.在左闭右开时，使用mid = low + (high - low) // 2，而不能使用使用mid = high - (high - low) // 2，因为(high - low) // 2是取整后的结果，high - (high - low) // 2可能造成mid偏大或者出现溢出，例如区间[3, 4)计算mid时，high - (high - low) // 2 = 4 - 0 = 4从而出现溢出。mid的计算必须从闭端出发向中心靠拢
但事实上，以上做法的本质似乎并不在于左闭右开，而是左闭右开促使我们的代码逻辑发生了变化。真正的本质在于代码逻辑的变化——
在左闭右开的情况下，实际上将常规的二分查找（会形成左子序列，中数，右子序列，这实际上是3分查找了）实现为真二分查找（只形成左子序列和右子序列），返回值index将会落在区间[low, high]里面，如果在index = high位置插入，这时是在数组的末尾append啦，也就是闭端对应的位置
从左闭右开体会相遇指针的精髓【由上延申】
左闭右开写二分简洁高效，本质上是因为【左闭+右开形成的区间覆盖了target可能的全部任意位置】
我们可以这样理解，不管是开还是闭，在程序里面其实都是一个指针嘛，指针并没有开闭之分，只是标记了一个位置，仅此而已。我把右指针指向原数组nums的最后一个元素后面，也就是index = len(nums)的地方，因为target完全可能在最后面插入的。这样它就能够和左指针协作，覆盖target可能的全部任意位置。这就是所谓的左闭右开的本质，例如数组[2,4,6,8,10]，right首先指向index=5，即10后面的位置，因为待插入元素可能的插入位置就是0-5。而如果我把右指针指向原数组nums的最后一个元素，等于使用双闭区间，不能覆盖完所有情况，相对更繁琐
认识到这一点之后，我们再看上面的所谓左闭右开的二分查找，说白了过程就是这样：
1.设置左右指针，指向待插入元素可能的插入位置的最小最大处，覆盖all situation
2.求得mid指针，将数组分为左右2部分，part_left = mid左 + mid，part_right = mid右
3.判断target在左还是右，然后重新调整左右指针的位置形成新的查找区间。直到左右指针重合即为所求位置
summary：到这里，我们可以抛弃区间开闭论，而改为理解成：用左右指针去标记可能的上下界，让其相遇命中位置
例题：
leetcode33.查找旋转有序数组
https://leetcode-cn.com/problems/search-in-rotated-sorted-array
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的最小索引，否则返回 -1。要求时间复杂度O(logn)
【相似的题目还有leetcode153, 154】
思路：
时间复杂度O(logn)，肯定是要分治，上二分查找
二分查找？这里不是完全有序可以吗？可以啊。这里一定要理解到位，二分查找并不要求整个数组完全有序，【而是要求每一次二分后可以定位target到底在左侧还是右侧，只要能定位target在哪部分就可以】。而整个数组有序是见的最多的方便定位target的场景
这里我们同样能够二分后定位target，只不过要多一点判断
注意一下，按题目要求，如果数组中存在这个目标值，则返回它的最小索引，否则返回 -1，因此right指针初始时应该指向index = len(nums)-1
解法1：比较mid和left指向元素的大小，来确认旋转数组的有序部分
class Solution:
def search(self, nums: List[int], target: int) -> int:
return self.biSearch(nums, 0, len(nums)-1, target)
def biSearch(self, nums, left, right, target):
if not nums:
return -1
while left < right:
mid = left + (right - left) // 2
# 左侧有序，注意：通过mid和left的大小关系来判断左侧有序，需要囊括等号情况，因为2个元素时，左偏的mid与left重合
if nums[mid] >= nums[left]:
# 如果target在左侧，搜左侧
if nums[left] <= target <= nums[mid]:
right = mid
else:
left = mid + 1
# 右侧有序
else:
# 在右侧搜
if nums[right] >= target > nums[mid]:
left = mid + 1
else:
right = mid
# left对应target在数组中的插入位置
if nums[left] != target:
return -1
return left
解法2：比较mid和right指向元素的大小，来确定旋转数组的有序部分
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
l, r = 0, len(nums)-1
while l < r:
mid = l + (r-l) // 2
if nums[mid] < nums[r]:
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid
else:
if nums[l] <= target <= nums[mid]:
r = mid
else:
l = mid + 1
if nums[l] == target:
return l
return -1
leetcode 162. 寻找峰值
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。nums可以存在多个峰值，返回其中一个的index即可，你可以假设 nums[-1] = nums[n] = -∞。要求时间复杂度O(logN)
思路：
看到时间复杂度O(logN)，不用想肯定是分治，二分查找。
根据写二分查找的3个步骤，
1.确定可能的index的上下界，显然有left = 0，right = len(nums) - 1
2.求出mid，然后将区间划分为2部分，mid根据需要划归入左区间或者右区间
3.确定是要往左区间搜索，还是往右区间搜索，
规律一：如果nums[i] > nums[i+1]，则在i之前（包含i）一定存在峰值元素
规律二：如果nums[i] < nums[i+1]，则在i+1之后（包含i+1）一定存在峰值元素
然后调整left或right指针，直到left == right
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
if not nums:
return -1
new_list = [-float('inf')] + nums + [-float('inf')]
return self.biSearch(new_list, 0, len(new_list)-1) - 1
def biSearch(self, nums, left ,right):
while left < right:
mid = left + (right - left) // 2
# 注意，mid - 1不一定在当前的left和right范围内，但mid+1一定在，所以用mid和mid+1做比较
if nums[mid] > nums[mid + 1]:
right = mid
elif nums[mid] < nums[mid + 1]:
left = mid + 1
return left
在峰值上我们再上点难度
leetcode1095. 山脉数组中查找目标值
虽然难度是hard，但是在掌握了二分查找的模板下，就是easy，一次ac了
思路：
先利用二分查找，找到MountainArray的峰值
找到峰值后，在左侧上升区间找一次target，在右侧下降区间也找一次target，比较2个查找结果即可
下面额外定义了3个findxxx方法，用于找峰值点，增区间找target和减区间找target，都是基于相遇指针的二分查找算法，结构一样，大同小异
# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
# def get(self, index: int) -> int:
# def length(self) -> int:
class Solution:
def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
peak_index = self.findPeak(mountain_arr)
res1 = self.findInLeft(target, mountain_arr, peak_index)
res2 = self.findInRight(target, mountain_arr, peak_index)
if res1 != -1:
return res1
if res2 != -1:
return res2
return -1
# 找峰值点
def findPeak(self, mountain_arr: 'MountainArray'):
right = mountain_arr.length() - 1
left = 0
while left < right:
mid = left + (right - left) // 2
a, b = mountain_arr.get(mid), mountain_arr.get(mid+1)
if a < b:
left = mid + 1
elif a > b:
right = mid
return left
# 在峰值左边找
def findInLeft(self, target: int, mountain_arr: 'MountainArray', peak_index):
right = peak_index
left = 0
while left < right:
mid = left + (right - left) // 2
a, b = mountain_arr.get(mid), mountain_arr.get(mid+1)
if a < b:
if target <= a:
right = mid
else:
left = mid + 1
elif a > b:
if target < a:
left = mid + 1
else:
right = mid
if target == mountain_arr.get(left):
return left
return -1
# 在峰值右边找
def findInRight(self, target: int, mountain_arr: 'MountainArray', peak_index):
right = mountain_arr.length() - 1
left = peak_index
while left < right:
mid = left + (right - left) // 2
a, b = mountain_arr.get(mid), mountain_arr.get(mid+1)
if a < b:
if target <= a:
right = mid
else:
left = mid + 1
elif a > b:
if target < a:
left = mid + 1
else:
right = mid
if target == mountain_arr.get(left):
return left
return -1
再看一道更加隐晦一点的二分查找
1011. 在 D 天内送达包裹的能力
思路：根据题意，结果一定落在【max(weights), sum(weights）】这个区间之间，因为左端点对应每天一条船，右端点对应只有一条超级大船。 然后利用二分法，每一次循环模拟运货的过程，然后根据需要的天数与 输入 D 的关系来调整区间左右端点。
class Solution(object):
def shipWithinDays(self, weights, D):
"""
:type weights: List[int]
:type D: int
:rtype: int
"""
lo, hi = max(weights), sum(weights)
while(lo < hi):
mid = (lo + hi) // 2 # mid 即为当前运送的capacity
#------以下为模拟运货的过程，temp表示当天这条船承载的重量，day表示已用的天数-------
temp = 0
day = 1
for weight in weights:
temp += weight
if temp > mid:# 当前货运不动 需要新的一艘船才行
day += 1
temp = weight
#------以上为模拟运货的过程-----------------
if day > D: # 当前的capacity太小了，不够，需要更大容量才能及时运完
lo = mid + 1
elif day <= D:
hi = mid
return lo
基于相遇指针的二分查找模板（本文核心）
def biSearch(nums, left, right, target):
while left < right:
# mid指针
mid = left + (right - left) // 2
# 二分为左右两侧
# 判断要去左侧搜还是去右侧搜，然后调整指针
# 如果在右侧
if target in right side:
left = mid + 1
# 如果在左侧
else:
right = mid
return left
