[数据结构与算法]Leetcode 704 二分查找

1.题目要求

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

2.思路分析

二分查找只有一个思想，那就是：逐步缩小搜索区间。

在升序数组 nums 中寻找目标值 target，对于特定下标 i，比较 nums[i] 和 target 的大小：

• 如果 nums[i]=target，则下标 i 即为要寻找的下标；

• 如果 nums[i]>target，则 target 只可能在下标 i 的左侧；

• 如果nums[i]<target，则 target 只可能在下标 i 的右侧。

不管是哪一种模板，都不会回答看到的 mid 的值以后如何设计条件，把区间进行正确的划分，以及：

• 在某种条件下，mid 的值是否可以取到；
• 下一轮搜索是在 mid 的左边还是右边继续查找。

3.代码实现

# 写法一:
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        # 在区间 nums[left..right] 里查找等于 target 的元素的下标
        # 退出循环的时候有 left == right 成立
        # 好处是：不用判断应该返回 left 还是 right；
        while left < right:
            mid = (left + right) // 2
            # 下一轮搜索区间是[left..mid]
            if nums[mid] > target:
                right = mid
            # 下一轮搜索区间是[mid+1..right]
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        return -1
    
# 写法二:
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        # # 在区间 nums[left..right] 里查找等于 target 的元素的下标
        while left <= right:
            mid = (left + right) // 2
            # 下一轮搜索区间是[left..mid-1]
            if nums[mid] > target:
                right = mid -1 
            # # 下一轮搜索区间是[mid+1..right]
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
        return -1

4.复杂度分析

• 时间复杂度：O(logn)，其中 n 是数组的长度。
• 空间复杂度：O(1)。

5.关于二分查找的疑问

1.为什么在题解里 while (left < right) 表示左闭右闭区间?

? while (left < right) 不表示搜索区间为「左闭右开」，这一点没有根据。真正应该看边界如何设置，这一点完全是人为定义。

? 表示一个区间，最直接的表示就是左闭右闭区间。例如：我们想表示搜索的范围是 1, 2, 3, 4, 5, 6, 7, 8, 9 ，很自然地会表示成 [1…9] ，我们也会说这些数是 1 到 9 之间的数，包括 1 和 9。正常情况下，不会说：这些数在 1 到 10 之间，不包括 10；

? 只看到 while (left < right) 里的 < ，不能说明右边界不能取到。真正看区间表示应该看左右边界到底如何设置，如果我们分析出下一轮搜索的范围是 [left…mid] 而设置 right = mid + 1，才表示搜索区间为「左闭右开」区间 。这是因为 [left…right) = [left…mid + 1) = [left…mid]。

2. 为什么有一些二分查找取 mid 的时候，括号里要加 1?

? 因为 int mid = (left + right) / 2 在区间里有偶数个元素的时候，mid 只能取到位于左边的中间数，要想取到位于右边的中间数，就需要在括号里加 1。

为什么要取右边中间数呢？这是因为在区间里 只有 2 个元素的时候，把 [left…right] 划分成 [left…mid - 1] 和 [mid…right] 这两个区间，int mid = (left + right) / 2 这种取法不能把搜索区间缩小。

总之就是为了：避免死循环。

3. 什么时候 right 取 len ？什么时候 right = len - 1？

看题目，每个问题的答案都未必一样。