[704][中等][二分] 二分查找

题目描述

704. 二分查找

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

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

• 你可以假设 nums 中的所有元素是不重复的。

• n 将在 [1, 10000]之间。

• nums 的每个元素都将在 [-9999, 9999]之间。

解题思路

二分查找详解.

两种终止条件带来的细节变化

要注意, right的起始位置, while循环的终止条件, left和right移动规则等细节之间, 是相互关联的.

本题中, 如果假设while的终止条件为left <= right, 相当于left和right定义的区间[left, right]两端都有效, 是闭区间, 因此在初始化right时, 应初始化为n - 1, n是列表的长度.

而且由于左右端都是闭的, right在移动时, 应当为right = mid - 1, 因为nums[mid]经过检测不符合条件, 不能被包含在下一个区间之内.

对应的代码为:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

但如果while的终止条件为left < right, 换句话说当left == right时就终止了, 可以认为right代表的位置是无效的, 越界的, 因此left与right相等时, 代表都越界了, 从而停止. 它们定义的区间为[left, right), 左闭右开. 而且在初始化right时, 因为要求越界, 应初始化为n.

另外, 在移动right时, 当mid位置的数值无效, 应当移动right时, 应当为right = mid, 当前mid位置是经过判别无效的, 因此放弃这个位置, 为新区间的开边界.

但需要注意的是, 如果left == right是通过移动right得到的, 那么在while停止的时候, left(也即mid和right)的位置是没有经过判别的, 因此在最后返回之前, 要再对这个位置单独的进行一次判别.

对应的代码为:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left if nums[left] == target else -1

寻找左侧边界的二分搜索

对于有序数组nums = [1,2,2,2,3], target为2, 使用上面任何一种方法得到的索引结果都是2, 即三个2中间的2对应的索引. 但如果要求变为, 对于重复的数字, 返回最左侧的索引呢?

第一个变化是, 当我们遇到nums[mid] == target时, 不能直接就返回了, 而是应该继续搜索. 关键问题是当遇到相等的情况, 应当怎么移动.

无论终止条件是left < right或left <= right, 在遇到nums[mid] == target时, 都应当移动right, 且移动的方法与nums[mid] > target的情况保持一致, 即:

• 终止条件是left < right: right = mid

• 终止条件是left <= right: right = mid - 1

对于第一种情况(left < right), 遇到target在列表中有多个值的情况, right在遇到target值之后, 只会逐渐向左移动, 直到移动到最左侧的target位置, 之后right就不可能再动了, 因为会一直满足nums[mid] < target, 导致left一直右移, 直到left == right结束.

第二种情况(left <= right), 在遇到target值之后, right也是会一直向右移动, 但与第一种情况不同的是, right一直在当前target之前的一位, 直到移动到最左侧的target前一位, 之后就是同样的left不断左移, 直到left > right, 即left == right + 1结束, 此时的left就是最左侧target的位置.

第一种情况(left < right)代码:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                right = mid
            elif nums[mid] > target:
                right = mid
            elif nums[mid] < target:
                left = mid + 1

        if left == len(nums):
            return -1
        return left if nums[left] == target else -1

第二种情况(left <= right)代码:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                right = mid - 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1

        if left == len(nums):
            return -1
        return left if nums[left] == target else -1

寻找右侧边界的二分查找

分析同上, 只是遇到相等的情况, 需要移动left.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid
            elif nums[mid] < target:
                left = mid + 1

        if left == 0:
            return -1
        return left - 1 if nums[left - 1] == target else -1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1

        if left == 0:
            return -1
        return left - 1 if nums[left - 1] == target else -1