day01 代码随想录算法训练营 704. 二分查找-526互联

题目：

leetcode 704. 二分查找

感悟：

困扰我多年的二分查找对于边界的判断，我终于理解了。

难点：

难点1：定边界right

right = len(nums)还是len(nums)-1

难点2：while循环

while left < right 还是 left <= right

难点3：mid取值

mid = right -1 还是mid = right

结论：

1.自己确定是左闭右闭[] ，还是左闭右开[)

2.根据自己的区间，来写循环和判断

实例1：

写左闭右闭的时候[1,1]，会取到右边

难点1：定边界right

是len(nums) -1
因为会取到右边。nums[right] 不能越界，索引从0开始

难点2：while循环

是<=
因为可以取到右边

难点3：mid取值

mid 取right-1
因为targht>nums[mid]时，已经包含右边的情况，无需再取中间值了。

完整代码：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 左闭右闭 [1,1]
        left = 0
        right = len(nums) -1 # 最后一位会取到
        while left <= right:
            mid = (left + right)//2
            if nums[mid] > target:
                right = mid -1
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        return -1

通过截图：

实例2：

写左闭右开区间[1,1)，不会取到右边界

难点1：定right边界

right = len(nums)
因为不会取到右边界

难点2：while循环

left < right
因为不会取到右边界，必定小于。不能既要取1，又不取1。所以必定小于

难点3：mid值

mid = right
不会取到右边界，自然可以等于

完整代码：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 左闭右开的写法 [1,1)
        left = 0
        right = len(nums)   # 因为取不到后面这个,所以可以等于
        while left < right: # 设置为左闭右开
            mid = (left + right) // 2
            if nums[mid] >target:
                right = mid     # 每次都取不到后面,所以这里等于mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        return -1

通过截图：