二分法
1、数组为有序数组 2、区间优先选择左闭右闭的区间，0---len（nums）-1 3、每个middle做对比的情况下都要进行边界条件更新，除非直接满足条件return。middle大：更新right = middle - 1，middle小：更新left = middle + 1 4、多考虑边界条件，高含金量：搜索左边界，搜索右边界
# 704.二分查找.py
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
middle = (left + right) // 2
if nums[middle] < target:
left = middle + 1
elif nums[middle] > target:
right = middle - 1
else:
return middle
return -1# 35.搜索插入位置.py
# 最终版
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) -1
while left <= right: # 为什么是必须考虑等于的情况？因为这是一个左右都闭合的空间。在查找时即使左右已经相等，也需要进行加减1，变成left比right大的情况
middle = (left + right) //2
if nums[middle] == target:
return middle
elif nums[middle] > target:
right = middle - 1
elif nums[middle] < target:
left = middle + 1
return right + 1 # 为什么不是left-1？因为此时left已经比right大了，right在左边，当然是左+1
# 34.在排序数组中查找元素的第一个和最后一个位置.py
class Solution:
def searchRange(self, nums: list[int], target: int) -> list[int]:
def searchLeft(nums:list[int], target:int) -> int: # 寻找左边界
leftBorder = -10
left, right = 0, len(nums) - 1
if len(nums) == 0:
return [-1, -1]
else:
while left <= right:
middle = (left + right) // 2
if nums[middle] < target:
left = middle +1
elif nums[middle] == target:
right = middle - 1
leftBorder = right # 为什么不是middle？因为计算出来的左边界是不包含target的右边界
elif nums[middle] > target:
right = middle - 1 # 重建左边界不断逼近实际左边界
leftBorder = right # 如果target在nums的左边，middle永远大于target，leftBorder变为-1
return leftBorder
def searchRight(nums:list[int], target:int) -> int:
rightBorder = -10
left, right = 0, len(nums) - 1
while left <= right:
middle = (left + right) // 2
if nums[middle] > target: # 如果target在nums的左边，middle永远大于target，此时leftBorder为-1，rightBorder的更新条件不会被触发，所以最后的rightBorder为初始值-10
right = middle - 1
elif nums[middle] < target:
left = middle + 1
rightBorder = left # 为什么不是middle？
elif nums[middle] == target:
left = middle +1
rightBorder = left
return rightBorder
leftBoder = searchLeft([1,2,2,2,2,3,4,5,6], 2)
print(leftBoder)
rightBoder = searchRight([1,2,2,2,2,3,4,5,6], 2)
print(rightBoder)
if leftBoder == -10 or rightBoder == -10: # 但凡有一个初始值没被改变的，就返回[-1, -1]
return [-1, -1]
if rightBoder - leftBoder > 1: # 为什么没有等于？ 如果target卡在中间而且没有相同的值的时候，rightBoder - leftBoder应该等于1，应该返回[-1, -1]*****大于1说明存在有意义的左右边界值
return [leftBoder + 1, rightBoder - 1] # 因为计算出来的右边界是不包含target的右边界
return [-1, -1]# 69.x的平方根.py
# # 参考
# class Solution:
# def mySqrt(self, x: int) -> int:
# l, r, ans = 0, x, -1
# while l <= r:
# mid = (l + r) // 2
# if mid * mid <= x:
# ans = mid
# l = mid + 1
# else:
# r = mid - 1
# return ans
# # 提交版
# class Solution:
# def mySqrt(self, x: int) -> int:
# left, right, ans = 0, x, -1
# while left <= right:
# middle = (left + right) // 2
# if middle * middle == x:
# ans = middle
# # 为什么等于的时候还要更新左边界？即使等于x了，也要继续进行循环，要是不更新left的值那就永远都循环下去了，所以不管什么情况都要更新边界条件
# left = middle + 1 # 如果不想更新了，也可以直接return ans，没问题
# elif middle * middle < x:
# ans = middle
# left = middle + 1
# elif middle * middle > x:
# # ans = middle # 当尝试的middle平方大于x时，并不需要储存ans，首先是因为这个middle绝对不可能是解，其次假如最后一次尝试是这个情况的话，会更新成错误的ans
# right = middle -1
# return ans
# # 调试
# def mySqrt(x: int) -> int:
# left, right, ans = 0, x, -1
# while left <= right:
# middle = (left + right) // 2
# if middle * middle == x:
# ans = middle
# # left = middle + 1
# elif middle * middle < x:
# ans = middle
# left = middle + 1
# elif middle * middle > x:
# # ans = middle
# right = middle -1
# return ans
# print(mySqrt(4))
# 二刷:问题出在了left = middle + 1，写成减号了，另外ans = middle；return ans不能写成return ans == middle，进一步探索
class Solution:
def mySqrt(self, x: int) -> int:
left, right, ans = 0, x, -1
while left <= right:
middle = (left + right) // 2
if middle * middle == x:
ans = middle
return ans
elif middle * middle > x:
right = middle - 1
elif middle * middle < x:
ans = middle
left = middle + 1
return ans# 367.有效的完全平方数.py
# 参考
class Solution:
def isPerfectSquare(self, num: int) -> bool:
left, right = 0, num
while left <= right:
mid = (left + right) // 2
square = mid * mid
if square < num:
left = mid + 1
elif square > num:
right = mid - 1
else:
return True
return False
# 1.0 一遍通过
class Solution:
def isPerfectSquare(self, num: int) -> bool:
left, right = 0, num
while left <= right:
middle = (left + right) // 2
if middle * middle == num:
return True
elif middle * middle > num:
right = middle - 1
elif middle * middle < num:
left = middle + 1
return False