数组

二分法查找

前提

1. 数组为有序数组；
2. 数组中没有重复元素。

优点
逻辑简单

难点
涉及很多边界条件，对区间定义不清楚，二分法则容易写乱

解决方法:

原则： 循环不变量规则

二分查找中，保持区间不变量，在循环寻找中每一次边界的处理都要坚持区间的定义来操作，

方式：

1. 左闭右闭

2. 左闭右开

左闭右闭

第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。

区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

• while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
• if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

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

左闭右开

如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。

有如下两点：

• while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
• if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

class Solution:
    
    def search(self, nums: List[int], target: int)->int:
        """
        左闭右开
        """
        if not nums:
            return -1
        l = 0
        r = len(nums) - 1
        while l <= r:
            m = round(l+(r-l)/2)
            if nums[m] == target:
                return m     
            elif nums[m] > target:
                r=m-1
            else:
                l=m+1
        return -1