Leetcode 704 二分查找

题目链接：704 二分查找

关键点思路:

1、是否要进入到 while 部分的代码是 left <= right 还是 left < right, 看 [left, right] 是否是合法区间. 例如 [1, 1] 是合法区间，取<=; [1, 1) 非合法区间，取 < 。

2、缩小区间时，考虑边界是否已经比较过。

左闭右闭区间 [left, right]

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1
        while l <= r:                # 左闭右闭区间
            mid = (l+r) // 2
            if target < nums[mid]:   # mid 已经比较过，所以缩小区间取 mid - 1
                r = mid - 1
            elif target > nums[mid]:  # mid 已经比较过，所以缩小区间取 mid + 1
                l = mid + 1
            else:
                return mid
        return -1

左闭右开区间 [left, right)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)  # 左闭右开，避免错过最右端的元素
        while l < r:   # 采用左闭右开原则 [l, r)
            mid = (l+r) // 2
            if target < nums[mid]:
                r = mid                 # 缩小区间，右边为开区间
            elif target > nums[mid]:
                l = mid + 1             # 缩小区间，左边为闭区间，去除已比较过的 mid
            else:
                return mid
        return -1