二分查找模板
代码语言：javascript复制def binarySearch(nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = (right left) // 2
if nums[mid] == target:
return True
elif nums[mid] < target:
left = mid 1
else:
right = mid - 1
return False
nums = [1,2,3,4,5,7]
res = binarySearch(nums, 7)
print(res)寻找左侧边界的二分查找
代码语言：javascript复制def binarySearch(nums, target):
left = 0
right = len(nums)
while left < right:
mid = (right left) // 2
if nums[mid] == target:
right = mid
elif nums[mid] < target:
left = mid 1
else:
right = mid
if left == len(nums):
return -1
if left == 0 and nums[left] != target:
return -1
return left
nums = [1,1,2,2,2,3]
res = binarySearch(nums, 2)
print(res)寻找右侧边界的二分查找
代码语言：javascript复制def binarySearch(nums, target):
left = 0
right = len(nums)
while left < right:
mid = (right left) // 2
if nums[mid] == target:
left = mid 1
elif nums[mid] < target:
left = mid 1
else:
right = mid
if right >= len(nums) and nums[right - 1] != target:
return -1
return right - 1
nums = [1,2,2,2,2,3,3,4]
res = binarySearch(nums, -2)
print(res)当数组中存在重复的元素的时候，我们要返回左右边界的时候，当查找到该元素时，我们不能返回True或者Fasle，而是要不断的缩小边界。
包裹运输问题
def shipWithinDays(weights, d):
left = max(weights)
right = sum(weights) 1 # 船的载重区间[left,right)
while left < right:
mid = (right left) // 2
if canFinish(weights, d, mid):
right = mid
else:
left = mid 1
return left
def canFinish(w, d, cap):
i = 0
for day in range(d):
maxCap = cap
while maxCap - w[i] >= 0:
i = 1
if i == len(w):
return True
maxCap = maxCap - w[i]
return False该题代码还有点问题，没有通过leetcode上的全部用例，掌握思想就好。 最后，首先思考使用 for 循环暴力解决问题，观察代码是否如下形式：
代码语言：javascript复制for i in range(n):
if isOK(i):
return answer如果是，那么就可以使用二分搜索优化搜索空间：如果要求最小值就是搜索左侧边界的二分，如果要求最大值就用搜索右侧边界的二分。
labuladong的算法小抄
