二分法查找（左闭右开划分区间）

第一题

class Solution: def missingNumber(self, nums: List[int]) -> int: lo = 0 hi = len(nums) while lo < hi: mi = (lo + hi) // 2 if mi == nums[mi]: lo = mi +1 else: hi = mi return lo 

左闭右开的解法 [lo,hi) 表示待定的区间 [0,lo):表示等于的区间 [hi, len(nums) ) : 表示不等于的区间 

最后返回的lo->hi, 表示一个以lo的左侧的分界线，左侧都等于，右边都不等于
写代码时，以划分区间为起点，怎样的条件可以正确的划分区间。

第二题

class Solution: def search(self, nums: List[int], target: int) -> int: # 绝对小于 target lo = 0 hi = len(nums) while lo < hi: mid = (lo + hi) // 2 if nums[mid] < target: lo = mid+1 else: hi = mid
        x1 = lo # 绝对大于target lo = 0 hi = len(nums) while lo < hi: mid = (lo + hi) // 2 if target < nums[mid]: hi = mid else: lo = mid + 1 x2 = lo -1 return x2-x1+1 

用划分区间的方法，使用二分法，划分两次

本文地址：https://blog.csdn.net/qq_36275734/article/details/108238509