二分查找精炼回顾-kevin

二分搜索回顾，由于习惯问题， 二分搜索问题都采用闭区间来思考 二分搜索总共就三类问题，统一规范如下, 由于都统一采用闭区间来思考，所以while的判定条件都是**left <= right ** mid 在都是在while循环之后再更新

left = 0, right = len(nums) - 1
#所以二分搜索区间是[left, right]

1,寻找一个数

def binarySearch(nums:List[int], target:int) -> int:left = 0# 注意right = len(nums) - 1while left <= right:mid = left + (right - left) // 2if nums[mid] == target:return midelif nums[mid] < target:# 注意left = mid + 1elif nums[mid] > target:# 注意right = mid - 1

• 由于采用闭区间，[left, right]无意义的条件是是left = right + 1，所以while的判定条件是left <= right 时候进入循环，跳出循环的条件就是left = right + 1

• 由于采用都是闭区间，也就是发现mid 不是要查找的目标时候，由于闭区间应该更新为[left, right - 1] 或者更新为 [mid + 1, right] ，只要更新一定有1

• 更新自己总结的小口诀是, ‘大右，小左’ 解读是中间值比目标大，更新右侧边界 ， 中间值比目标小更新左侧边界如果nums[mid] > target更新left = mid + 1

  如果nums[mid] < target 更新 right = mid - 1

找边界问题的关键点在于，对nums[mid] == target这种情况的处理， 总结起来就是要找左边界，就是在[left, mid - 1] 中持续收缩，直到找到左边界，也就是>=这种 要找右边界，就是在[mid + 1, right] 中持续收缩，直到找到有边界。 所以当碰到目标值的时候，两者操作不同，获得边界自然就不同

2，寻找左侧边界

找左侧边界的特殊情况，如果 target 不存在，搜索左侧边界的二分搜索返回的索引是大于 target 的最小索引。

可见，找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid - 1] 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

if nums[mid] < target:# 搜索区间变为 [mid+1, right]left = mid + 1
elif nums[mid] > target:# 搜索区间变为 [left, mid-1]right = mid - 1
elif nums[mid] == target:# 收缩右侧边界right = mid - 1

3，寻找右侧边界

while left <= right:mid = left + (right - left) // 2if nums[mid] > target:right = mid - 1elif nums[mid] < target:left = mid + 1elif nums[mid] == target:left = mid + 1

总结

只要区间定义为闭区间，二分查找的判定条件就是 while left <= right ，其次，找边界问题与找点问题，不同点只在于num[mid] == target时候处理情况的不同。
用二分查找求最长递增子序列问题

class Solution:def lengthOfLIS(self, nums):top = [0] * len(nums)# 牌堆数初始化为 0piles = 0for i in range(len(nums)):# 要处理的扑克牌poker = nums[i]# 搜索左侧边界的二分查找（闭区间）left, right = 0, piles - 1#这个-1 经常遗漏。while left <= right:  # 注意这里是 <= 表示闭区间mid = (left + right) // 2if top[mid] > poker:right = mid - 1  # 继续在左半部分搜索elif top[mid] < poker:left = mid + 1  # 继续在右半部分搜索else:right = mid - 1  # 继续向左搜索# 没找到合适的牌堆，新建一堆if left == piles:piles += 1# 把这张牌放到牌堆顶top[left] = poker# 牌堆数就是 LIS 长度return piles