【二分查找】——旋转排序数组

153. 寻找旋转排序数组中的最小值

一、问题描述

已知一个长度为n的数组，预先按照升序排列，经由 1 到n次旋转后，得到输入数组。例如，原数组nums = [0,1,2,4,5,6,7]在变化后可能得到：若旋转 4 次，则可以得到[4,5,6,7,0,1,2]；若旋转 7 次，则可以得到[0,1,2,4,5,6,7]。注意，数组[a[0], a[1], a[2],..., a[n - 1]]旋转一次的结果为数组[a[n - 1], a[0], a[1], a[2],..., a[n - 2]]。

现在给你一个元素值互不相同的数组nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。要求找出并返回数组中的最小元素。必须设计一个时间复杂度为O(log n)的算法解决此问题。

二、示例说明

输入：nums = [3,4,5,1,2]，输出：1。
- 原数组为[1,2,3,4,5]，旋转 3 次得到输入数组，最小元素为1。
输入：nums = [4,5,6,7,0,1,2]，输出：0。
- 原数组为[0,1,2,4,5,6,7]，旋转 3 次得到输入数组，最小元素为0。
输入：nums = [11,13,15,17]，输出：11。
- 原数组为[11,13,15,17]，旋转 4 次得到输入数组，最小元素为11。

三、提示信息

n == nums.length：数组的长度。
1 <= n <= 5000：数组长度的范围。
-5000 <= nums[i] <= 5000：数组中元素的取值范围。
nums中的所有整数互不相同。
nums原来是一个升序排序的数组，并进行了 1 至n次旋转。

四、解题思路

由于要求时间复杂度为O(log n)，可以考虑使用二分查找。
数组经过旋转后被分为两个有序的部分，最小元素是两个有序部分的分界线。
通过比较中间元素与右边界元素的大小关系，可以确定最小元素在哪个部分。
如果中间元素大于右边界元素，说明最小元素在右半部分；否则，说明最小元素在左半部分或者就是中间元素。

五、代码实现

如果中间元素大于最右元素，说明旋转后的数组的最小值一定在右半边（且一定不为中间元素），移动左边界 $l e f t$ 到 $mi d + 1$
否则中间元素小于最右元素（题目要求输入数组不重复，所以不可能等于），说明最小值在左半边或者就是 $mi d$ ,所以移动右边界 $r i g h t$ 到 $mi d$ 。
不断重复以上判断，直到退出循环，输出此时的 $r i g h t$ 就是最小值！

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

错错错，right是最小值所在位置，nums[right]才是题目要求输出的最小值！必须注意，不然考试的时候紧张写不出！

以下是使用 Python 实现的代码：

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

33. 搜索旋转排序数组

难度升级，不找最小值了！找特定值target，

一、问题描述

整数数组 nums 按升序排列，数组中的值互不相同。在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k + 1],..., nums[n - 1], nums[0], nums[1],..., nums[k - 1]]（下标从 0 开始计数）。

现在给定旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

二、示例说明

输入：nums = [4,5,6,7,0,1,2]，target = 0，输出：4。
- 在给定的旋转后的数组中，目标值0的下标是4。
输入：nums = [4,5,6,7,0,1,2]，target = 3，输出：-1。
- 目标值3不在给定的旋转后的数组中。
输入：nums = [1]，target = 0，输出：-1。
- 数组中只有一个元素，且目标值不在其中。

三、提示信息

1 <= nums.length <= 5000：数组的长度范围。
-104 <= nums[i] <= 104：数组中的元素取值范围。
nums 中的每个值都独一无二。
题目数据保证 nums 在预先未知的某个下标上进行了旋转。
-104 <= target <= 104：目标值的取值范围。

四、解题思路

一般看到有序序列，且要求时间复杂度为 O(log n)，大概率使用二分查找。
分析本题，由于数组在某个位置进行了旋转，原升序数组被分成了两个有序部分（其中一个可能为空）。
可以先利用上一题的方法找出最小值所在位置 $num_s$ ，结合最后一个值，确定 $t a r g e t$ 在[ $0$ ~ $s$ ]，还是[ $s$ ~ $n - 1$ ]
再进行一次二分搜索查找 $t a r g e t$
总共两次二分，第一次找最小值，第一次找目标值
分析这个思路的时间复杂度;你的思路是合理的，且时间复杂度满足 $O (l o g n)$ 。

首先分析找到最小值的过程：
- 在找最小值的过程中，使用二分查找。每次将搜索区间缩小一半，直到找到最小值。这个过程的时间复杂度为 $O (l o g n)$ 。因为每次比较中间值与右边界值，根据大小关系缩小搜索区间，最多进行 $l o g n$ 次比较就能找到最小值。
然后分析找目标值的过程：
- 确定了最小值所在位置后，将数组分为两个有序部分，再进行一次二分查找找目标值。同样每次将搜索区间缩小一半，时间复杂度也为 $O (l o g n)$ 。

所以总体来说，整个过程进行了两次二分查找，时间复杂度为 $O (l o g n) + O (l o g n) = O (l o g n)$ 。因为在大 $O$ 表示法中，多个对数级操作相加仍然是 $O (l o g n)$ 。

五、代码实现

利用上一题的思路找出最小值或对应索引，划分两个区间。

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

再次二分查找寻找target

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


    def search(self, nums: List[int], target: int) -> int:
        # 最小值位置索引
        min_s = findMin(nums)
        last_s = len(nums) - 1
        # 得到最小值和数组最后一个值
        min_num = nums[min_s]
        last_num = nums[last_s]
        # 根据target与最小值和末尾元素对比，确定其可能所在区间
        if target > min_num and target <= last_num:
            left = min_s + 1
            right = len(nums) - 1
        else:
            left = 0
            right = min_s
        
        # 进入第二次二分查找
        while left < right:
            mid = left + (right - left) // 2
            if mid < target:
                left = mid + 1
            else:
                right = mid
        if target == nums[right]:
            return right
        else:
            return -1
—————————————————————————————————————————————————————————————————————————————————————————————————————
NameError: name 'findMin' is not defined
            ^^^^^^^
    min_s = findMin(nums)
Line 15 in search (Solution.py)
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    ret = Solution().search(param_1, param_2)
Line 70 in _driver (Solution.py)
    _driver()
Line 85 in <module> (Solution.py)

这个错误是因为在search方法中调用了findMin函数，但findMin并不是在类的方法内定义的，所以不能直接通过findMin这样的方式调用。

可以将findMin方法定义在类中，或者在search方法中通过self.findMin(nums)这样的方式调用类的方法（前提是findMin是在类中定义的）。以下是修改后的代码：

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


    def search(self, nums: List[int], target: int) -> int:
        # 最小值位置索引
        min_s = self.findMin(nums)
        last_s = len(nums) - 1
        # 得到最小值和数组最后一个值
        min_num = nums[min_s]
        last_num = nums[last_s]
        # 根据target与最小值和末尾元素对比，确定其可能所在区间
        if target > min_num and target <= last_num:
            left = min_s + 1
            right = len(nums) - 1
        else:
            left = 0
            right = min_s
        
        # 进入第二次二分查找
        while left < right:
            mid = left + (right - left) // 2
            if mid < target:
                left = mid + 1
            else:
                right = mid
        if target == nums[right]:
            return right
        else:
            return -1
————————————————————————————————————————————————————————————————————————————————————————————————————————
解答错误
113 / 196 个通过的测试用例

输入
nums =[4,5,6,7,0,1,2]
target = 0

输出
-1
预期结果
4

又粗心了！
问题可能出在以下几个地方：

在第二次二分查找中，判断条件应该是nums[mid] < target，而不是mid < target。因为要比较的是数组中的值与目标值，而不是中间索引与目标值。

以下是修正后的代码：

        # 进入第二次二分查找
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        if target == nums[right]:
            return right
        else:
            return -1
——————————————————————————————————————————————————————————————————————————————————————————————————————
解答错误
181 / 196 个通过的测试用例

输入
nums =[4,5,6,7,0,1,2]
target = 0

输出
-1
预期结果
4

接近满分了，到底是哪里出了问题呢？
通过力扣的添加测试用例功能，我发现当target=0时，就会错！？
又尝试了一下，这份答案的问题是无法找到负数和0的位置！~

这个问题并不是因为大于小于号不适用于负数。问题可能出在以下几个地方：

在判断目标值所在区间时可能存在错误。当目标值小于最小值时，应该正确地设置搜索区间为左半部分（从第一个元素到最小元素索引减一）。
在第二次二分查找中，当目标值等于中间值时，应该正确地返回中间索引。

以下是修改后的代码：

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

    def search(self, nums, target):
        # 最小值位置索引
        min_s = self.findMin(nums)
        last_s = len(nums) - 1
        # 得到最小值和数组最后一个值
        min_num = nums[min_s]
        last_num = nums[last_s]
        # 根据 target 与最小值和末尾元素对比，确定其可能所在区间
        if target > min_num and target <= last_num:
            left = min_s + 1
            right = len(nums) - 1
        elif target < min_num:
            left = 0
            right = min_s - 1
        else:
            left = min_s
            right = min_s

        # 进入第二次二分查找
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                return mid
        return -1
_____________________________________________________
是解决了找负数的问题，但是通过用例更低了......

猜测：问题出在了几个区间的划分！
逐一排查各个位置的代码：

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


    def search(self, nums: List[int], target: int) -> int:
        # 最小值位置索引
        min_s = self.findMin(nums)
        last_s = len(nums) - 1
        # 得到最小值和数组最后一个值
        min_num = nums[min_s]
        last_num = nums[last_s]
        # 根据target与最小值和末尾元素对比，确定其可能所在区间
        if target > min_num and target <= last_num:
            left = min_s + 1
            right = len(nums) - 1
        elif target < min_num:
            left = 0
            right = min_s - 1 
        else:
            return min_s
        
        # 进入第二次二分查找
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                return mid
        if target == nums[right]:
            return right
        else:
            return -1
————————————————————————————————————————————————————————————————————————————————
无语住了，通过用例下降到了109......

受不了了看看题解吧

class Solution:
    # 153. 寻找旋转排序数组中的最小值
    def findMin(self, nums: List[int]) -> int:
        left, right = -1, len(nums) - 1  # 开区间 (-1, n-1)
        while left + 1 < right:  # 开区间不为空
            mid = (left + right) // 2
            if nums[mid] < nums[-1]:  # 蓝色
                right = mid
            else:  # 红色
                left = mid
        return right

    # 有序数组中找 target 的下标
    def lower_bound(self, nums: List[int], left: int, right: int, target: int) -> int:
        while left + 1 < right:  # 开区间不为空
            mid = (left + right) // 2
            # 循环不变量：
            # nums[left] < target
            # nums[right] >= target
            if nums[mid] < target:
                left = mid  # 范围缩小到 (mid, right)
            else:
                right = mid  # 范围缩小到 (left, mid)
        return right if nums[right] == target else -1

    def search(self, nums: List[int], target: int) -> int:
        i = self.findMin(nums)
        if target > nums[-1]:  # target 在第一段
            return self.lower_bound(nums, -1, i, target)  # 开区间 (-1, i)
        # target 在第二段
        return self.lower_bound(nums, i - 1, len(nums), target)  # 开区间 (i-1, n)

一、整体架构

这段代码的目的是在旋转排序数组中查找目标值的索引，如果目标值不存在则返回 -1。它主要通过两个函数来实现这个目标：findMin和search。

二、findMin函数

初始化区间：
- 首先将区间初始化为开区间(-1, len(nums) - 1)，其中left初始化为 -1，right初始化为数组长度减 1。这个区间表示在整个数组范围内寻找最小值。
二分查找循环：
- 进入一个循环，条件是left + 1 < right，即当区间不为空时继续循环。
- 在每次循环中，计算中间位置mid为(left + right) // 2。
- 如果nums[mid] < nums[-1]，说明中间值小于数组最后一个元素，那么最小值在左半部分（包括中间值），所以将right更新为mid，缩小搜索区间到左半部分。
- 如果nums[mid] >= nums[-1]，说明中间值大于等于数组最后一个元素，那么最小值在右半部分，所以将left更新为mid，缩小搜索区间到右半部分。
返回最小值下标：
- 当循环结束时，区间长度为 1，此时right指向的位置就是最小值的下标，返回right。

三、lower_bound函数

初始化区间和循环不变量：
- 这个函数用于在给定区间内查找目标值的下界，即第一个大于等于目标值的元素的下标。
- 初始区间为(left, right)，其中left和right是传入的区间边界。
- 循环不变量为nums[left] < target和nums[right] >= target，这意味着在循环过程中，左边界的值始终小于目标值，右边界的值始终大于等于目标值。
二分查找循环：
- 进入一个循环，条件是left + 1 < right，即当区间不为空时继续循环。
- 在每次循环中，计算中间位置mid为(left + right) // 2。
- 如果nums[mid] < target，说明中间值小于目标值，那么更新左边界为mid，缩小搜索区间到(mid, right)。
- 如果nums[mid] >= target，说明中间值大于等于目标值，那么更新右边界为mid，缩小搜索区间到(left, mid)。
返回结果：
- 当循环结束时，区间长度为 1，此时如果右边界的值等于目标值，返回右边界下标，否则返回 -1。

四、search函数

找到最小值下标：
- 调用findMin函数找到旋转数组中的最小值的下标i。
判断目标值所在区间并进行二分查找：
- 如果目标值大于数组最后一个元素，说明目标值在第一段，调用lower_bound函数在开区间(-1, i)内进行二分查找。
- 如果目标值小于等于数组最后一个元素，说明目标值在第二段：
  - 如果i = 0，说明数组是递增的，直接在开区间(0, len(nums))内进行二分查找（实际上相当于在整个数组范围内查找）。
  - 如果i > 0，在开区间(i - 1, len(nums))内进行二分查找。
- 这两种情况可以合并成在(i - 1, len(nums))区间内进行二分查找。