文章目录
二分查找框架
def binarySearch(nums,target):
left,right = 0,...
while ...:
mid = left + (right - left) // 2
if nums[mid] == target:
...
elif nums[mid] < target:
left = ...
elif nums[mid] > target:
right = ...
return ...查找一个数
def binarySearch(nums,target):
left,right = 0,len(nums)-1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
return -1查找左边界,搜索区间[left,right)
def left_bound(nums,target):
if nums == []: return -1
left,right = 0,len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
elif nums[mid] < target:
left = mid + 1
return left
# 处理不存在target值
# if (left == len(nums)) return -1
# return nums[left] == target ? left : -1查找右边界,搜索区间[left,right)
def right_bound(nums,target):
if nums == []: return -1
left,right = 0,len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
elif nums[mid] > target:
right = mid
return left - 1
# 处理不存在target值
# if (left == 0): return -1
# return nums[left-1] == target ? left-1 : -1使用python bisect模块
import bisect
bisect.bisect_left(nums,target) # 返回第一个target的坐标（左边界）
bisect.bisect_right(nums,target) # 返回最后一个target的坐标+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[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
return -1
s = Solution()
s.search([-1,0,3,5,9,12],9)
s.search([-1,0,3,5,9,12],2)在排序数组中查找元素的第一个和最后一个位置（中等）
来自算法小抄
找左边界和右边界
class Solution:
def searchRange(self, nums, target):
# 分别找左右边界
# 找左边界
def binnary_search_left(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] == target:
right = mid
elif nums[mid] > target:
right = mid
elif nums[mid] < target:
left = mid + 1
return left
# 找右边界
def binnary_search_right(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] == target:
left = mid + 1
elif nums[mid] > target:
right = mid
elif nums[mid] < target:
left = mid + 1
return left - 1
left,right = binnary_search_left(nums, target),binnary_search_right(nums, target)
return [-1,-1] if left > right else [left,right]
s = Solution()
s.searchRange([5,7,7,8,8,10],6)
s.searchRange([5,7,7,8,8,10],8)
s.searchRange([],0)搜索二维矩阵（中等）
class Solution:
def searchMatrix(self, matrix, target):
# 找左区间
def binnary_search_left(nums,target):
left,right = 0,len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] == target:
right = mid
elif nums[mid] > target:
right = mid
elif nums[mid] < target:
left = mid + 1
return left
def binnary_search(nums,target):
left,right = 0,len(nums)-1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
elif nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
return False
if matrix == [] or matrix == [[]]: return False
nums = [i[0] for i in matrix]
row = binnary_search_left(nums,target)
if row >= len(matrix) or matrix[row][0] > target: row -= 1
return binnary_search(matrix[row],target)
s = Solution()
s.searchMatrix([[1],[3]],1)
s.searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]],11)
s.searchMatrix([[1]],1)搜索二维矩阵II（中等）
逐行二分搜索
class Solution:
def searchMatrix(self, matrix, target):
def binnary_search(nums,target):
left,right = 0,len(nums)-1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
elif nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
return False
res = False
for i in range(len(matrix)):
res = res or binnary_search(matrix[i],target)
return res
s = Solution()
s.searchMatrix([[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],20)