1.1前言：
在进阶之前可能很多学过二分法的人都认为二分查找十分简单，但事实不完全如此。比如你是否熟练的知道while 的条件有等于时返回究竟是mid 还是left，还是right，还是随便返回一个没有等于时又是返回什么……本文将给大家讲解二分法的进阶和bisect库函数的运用，并且再讲解之后我们会右Leetcode的配套练习题进行课后练习，当然我们也会带一下二分法的基础，以便无论你是否了解二分法都能快速上手。
使用二分法一定有一个十分重要的原则，就是待查找的数据必须是有序的，划重点，补充讲解一下在Leetcode常用的非递增和非递减，递增递减。
非递减：1 2 3 5 5 6 9 9 11 11
非递增：9 9 8 8 6 5 4 3 2 1 1
递增： 1 2 3 4 5 6 7 8 9
递减： 9 8 7 6 5 4 3 1
1.2二分查找（Binary Search）概述:
前提是在一个排好序列的列表中，二分查找是一种折半查找，从有序的列表初始候选区li[0:n]开始，通过对待查找的值与候选区的值比较，可以使候选去减少一半，最终找到想要的值，例如我们查找7
先判断Left和Right指向的值是否是目标值，7在mid的右边那么我们让Left指到middle+1，middle=（left+right）//2
同理在进行上述操作
找到了那么指导Left和Right相同如果找到的值和目标值相等则找到，如果不相等，那么就没有找到
代码实现
def binary_search(li,val):
left = 0
right = len(li)-1
while left<=right:
mid = (left+right)//2
if li[mid] == val:
return mid
elif li[mid]>val:
right = mid - 1
else:
right = mid + 1这里也有一篇包含查找，排序等多种算法的野生博客，大家可以放心食用：
1.3二分法进阶：
二分法其实思路十分简单，但是难在细节上，或许你每次总是在二分查找种不知道答案应该是返回left还是right 或者mid时候也可以，那么这篇博客二分法进阶主要就是要去理解细节左右边界。
1.31左闭右闭 [ left , right ]:
以寻找7为例子
即使这样注意while还没有结束：
这样才算是彻底的结束，所以此时如果你要返回right显然不是答案，在左闭右闭的区间要么返回right是错误的 ，
补充：如果这个数字target数字是7.5那么移动的就是，同样left指向的适合插入的索引而mid和right显然不是我们的答案。
nums = [1,2,3,4,5,6,7,8,9,11]
def binarysect_(nums,target):
left = 0
right = len(nums) - 1
while left <= right: #区间不为空
mid = (left + right) // 2
#注意这个地方在C语言和Java等语言种这样会出现数据溢出
#为了避免这个情况可以这样写：mid = left + (right - left )//2
if nums[mid] < target:
left = mid + 1 #搜索区间变成[mid+1,right]
else:
right = mid - 1 #搜索区间变成[left , mid-1]
return left
print(binarysect_(nums,7))
如果找 7 的话返回的是索引6刚好是对的，如果查找的 7.555，那么返回索引 7 刚好是适合插入的位置。
小结：如果是左闭右闭，while判断条件是 left <= right , 并且注意right = length - 1,答案返回left
1.32左闭右开[ left, right ) :
还是以找 7
那么在这种左闭右开的情况下发现 left right 都是指向同一个值，所以在这种情况下返回right 和left 都是可以的，但是mid不行，虽然在这种情况下可以但是如果target = 7.555时，mid 不符合要求，但是left和right 都是返回的适合插入的索引。
nums = [1,2,3,4,5,6,7,8,9,11]
def binarysect_(nums,target):
left = 0
right = len(nums)
while left < right: #区间不为空
mid = (left + right) // 2
#注意这个地方在C语言和Java等语言种这样会出现数据溢出
#为了避免这个情况可以这样写：mid = left + (right - left )//2
if nums[mid] < target:
left = mid + 1 #搜索区间变成[mid+1,right)
else:
right = mid #搜索区间变成[left , mid )
'''
这个right = mid 而不是mid - 1 与上面区别开
'''
return left
print(binarysect_(nums,7))
小结：如果是左闭右开，while判断条件是 left < right , 并且注意right = length ,答案返回left 或者right都可以，但是记得每一次right的变化是变为mid 因为要保证是开区间
大家也可以实际操作一下，每一次都打印left 和right 来看一下结果
1.33左开右开（left, right）:
左开又开的写法是更加简洁的一,种，每次不用mid 加减1，这里就不图片演示了，但是记得这种情况只能返回right，另外两个（left , mid）都不能完全保证答案的正确，判断方法与上类似这里不再赘述，直接看总结
nums = [1,2,3,4,5,6,7,8,9,11]
def binarysect_(nums,target):
left = -1
right = len(nums)
while left + 1 < right: #区间不为空
mid = (left + right) // 2
#注意这个地方在C语言和Java等语言种这样会出现数据溢出
#为了避免这个情况可以这样写：mid = left + (right - left )//2
if nums[mid] < target:
left = mid #搜索区间变成(mid+1,right)
else:
right = mid #搜索区间变成(left , mid )
return right
print(binarysect_(nums,7))
小结：如果是左开右开，while判断条件是 left + 1 < right , 并且注意，left = -1, right = length ,答案只能返回right，且left 和right 变化都是mid 不用加减1。
小总结：以上三种二分法的写法萝卜青菜各有所爱，你选择你经常写的那种，并且要记住判断条件和left，right 维护方法，最后不同的二分法返回的是left还是right ，虽然如果数据在nums中存在返回mid有时也对，但是总归是不稳定，所以最稳定的就是记住自己写的哪一种对应的应该返回哪个指针即可。
2.1Bisect库：
在Python中右Bisect库其中有二分查找函数，可以用于所有使用二分法查找的问题，包括，bisect()
bisect_left() , bisect_right(), 当然了如果二分法没有找到目标元素 BIsect库也提供
bisect.insort() , bisect.insort_right, bisect.insort_left() 来执行相应的插入操作
2.2 二分查找函数介绍：
bisect( ) &bisect_right() &bisect_left():
对于上面哪个数组可以采用：
nums = [1,2,3,4,5,6,7,8,9,11]
from bisect import *
print(bisect(nums,7.5))
#结果是7，即使大于7.5的第一个下标，返回的是适合插入的索引
print(bisect(nums,7))
#结果是7，返回的是大于7的第一个下标
print(bisect_right(nums,7.5))
#结果是7，即使大于7.5的第一个下标，返回的是适合插入的索引
print(bisect_right(nums,7))
#结果是7，返回的是大于7的第一个下标
print(bisect_left(nums,7.5))
#结果是7，即使大于等于7.5的第一个下标，返回的是适合插入的索引
print(bisect_left(nums,7))
#结果是6，返回的是大于等于7的第一个下标
bisect.bisect和bisect.bisect_right返回大于x的第一个下标(相当于C++中的upper_bound)，bisect.bisect_left返回大于等于x的第一个下标 (相当于C++中的lower_bound)。
如果nums中没有相应的值，bisect( ) &bisect_right() &bisect_left()也同样满足上述的返回原则
Eg1: bisect() 函数对于数字表查询也是适用的。 这个例子使用bisect()根据一组有序的数字划分点来查找考试成绩对应的字母等级: (如) 90 及以上为 'A'，80 至 89 为 'B'，依此类推:
>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
... i = bisect(breakpoints, score)
... return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']扩展知识：bisect（）三个函数实际上是有不知两个参数
bisect.bisect_left(a, target, lo=0, hi=len(a), *, key=None)a ：是要查找的已经排序后的数据
target : 目标元素
lo：开始查找的索引位置
hi : 查找的边界
key ： 指定带有单个参数的key function 用来从数组的每个元素中提取比较键 如下
nums = [ [1,2 ] [2,4 ] [3,5 ] [7,6 ] [8,9 ] [10,22 ] [11,15 ] [12,55 ] ]
那么我们怎么按照每一个 [ ] 中第一个元素来二分查找呢 可以令key = lambda x: x[0]
bisect.bisect_left(nums, 7, lo=0, hi=len(a), key=lambda x : x[0])2.23二分查找插入函数insort():
注意bisect库下的插入函数要和和list中的insert()区别开，由于前者bisect.insort()会先经过二分法查找到合适插入位置，所以时间复杂度O(log n)而后者在最坏的情况下是O(n)时间复杂度。
不过insort和bisect()用法几乎一摸一样，唯一的区别就是bisect()没有插入数据进去，同时,bisect.insort(), 和bisect.insort_right() 插入位置都是大于target 的索引，bisect.insort_left() 插入位置都是大于等于target 的索引:
nums = [1,2,3,4,5,6,7,8,9,11]
from bisect import *
insort_left(nums,7.5)
print(nums)
#其结果是[1, 2, 3, 4, 5, 6, 7, 7.5, 8, 9, 11]3.1Leetcode例题运用：
Eg:1二分查找：（如果你还没有试过一行流可以来试试这个题目）
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
class Solution:
def search(self, nums: List[int], target: int) -> int:
return -1 if target not in nums else bisect_left(nums,target)给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
from bisect import bisect_left
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if target not in nums:
return [-1,-1]
start = bisect_left(nums,target) ##直接运用库函数
ans = [start ,start]
if len(nums) - 1 == start: #注意一种特殊情况就是target 刚好就在末尾
return ans
for c in nums[start+1:]:
if c == target:
ans[1] += 1
return ans #这样写速度是最快的Eg 4 :摘水果：在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ，其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。fruits 已经按 positioni 升序排列 ，每个 positioni 互不相同 。
另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 ，就记作 一步 。你总共可以走 最多 k 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。
返回你可以摘到水果的 最大总数 。
输入：fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
输出：9
解释：最佳路线为：向右移动到位置 6 ，摘到 3 个水果 向右移动到位置 8 ，摘到 6 个水果
移动 3 步，共摘到 3 + 6 = 9 个水果
class Solution:
def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
left = bisect_left(fruits,[startPos - k]) ###这里就运用到了二分法
right = bisect_right(fruits,[startPos])
ans = s = sum(c for _, c in fruits[left:right])
while len(fruits) > right and fruits[right][0] <= startPos + k:
s += fruits[right][1]
while fruits[right][0] * 2 - fruits[left][0] - startPos > k and fruits[right][0] - fruits[left][0] * 2 + startPos > k : #前面是先右在左，后者是先左后右
s -= fruits[left][1]
left += 1
ans = max(ans,s)
right += 1
return ans题解参考灵神：
由于只能一步步地走，人移动的范围必然是一段连续的区间。
如果反复左右移动，会白白浪费移动次数，所以最优方案要么先向右再向左，要么先向左再向右（或者向一个方向走到底）。
设向左走最远可以到达 fruits[left][0]，这可以用枚举或者二分查找得出，其中 left 是最小的满足
fruits[left][0]≥startPos−k
的下标。
假设位置不超过 startPos 的最近水果在 fruits[right][0]，那么当 right 增加时，left 不可能减少，有单调性，因此可以用同向双指针（滑动窗口）解决。不了解的同学可以先看上面的视频讲解。
如何判断 left 是否需要增加呢？
如果先向右再向左，那么移动距离为
(fruits[right][0]−startPos)+(fruits[right][0]−fruits[left][0])
如果先向左再向右，那么移动距离为
(startPos−fruits[left][0])+(fruits[right][0]−fruits[left][0])
如果上面两个式子均大于 k，就说明 fruits[left][0] 太远了，需要增加 left。
对于 right，它必须小于 n，且满足
fruits[right][0]≤startPos+k
移动 left 和 right 的同时，维护窗口内的水果数量 s，同时用 s 更新答案的最大值