33. 搜索旋转排序数组

题目来源：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

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

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

解题思路

思路：二分查找

题目中，要求算法时间复杂度必须是 O(log n) 级别，在这里，其实提示可以使用二分查找的方法。

有个地方需要注意的是，二分查找，要求的是列表的元素必须是有序的。在这里，虽然原始数组是按照升序排序的，但数组在某个未知的点进行旋转之后，列表只有局部才是有序的。

但其实这里并不会冲突，因为将经过旋转的列表分割成两部分时，一定有一个部分是有序的。

直接以上面的示例 1 为例，[4, 5, 6, 7, 0, 1, 2]，如果将数组分割成 [4, 5, 6] 和 [7, 0, 1, 2]，那么前面 [4, 5, 6] 这部分是有序的。这在其他符合这些条件的数组一样是成立的。

上面提到数组分为两部分，那么可以考虑从在中点的位置进行划分，将原数组划分为 [left, mid] 和 [mid + 1, right] 两部分。

当将旋转后的数组分成上述两部分时，现在要考虑的就是 target 值，会落在哪个区间？当 target 值落在有序那部分的区间中，这个比较好理解，这个时候上下边界是确定的，题目中也说明【可以假设数组中不存在重复的元素。】，那么有且只有一个元素与之匹配。

现在具体分析判断 target 会落在哪个区间：

• 如果 [left, mid - 1] 这部分是有序的，且 target 落在 [nums[left], nums[mid]) 这个区间，那么就可以将搜索的范围缩小到 [left, mid - 1]，否则的话，将在 [mid + 1, right] 这个区间中进行搜索；
• 如果 [mid, right] 这部分是有序的，且 target 落在 (nums[mid+1], nums[right]]，那么就在 [mid + 1, right] 这个区间进行搜索，否则在 [left, mid - 1] 这个区间进行搜索。

下面是具体的代码实现。

代码实现

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # nums 为空时，直接返回 -1
        if not nums:
            return -1

        # 初始左右边界
        left, right = 0, len(nums) - 1
        
        # 判断哪部分区间是有序的
        # 判断 target 会落在哪个区间
        while left <= right:
            # 数组划分为两部分
            mid = (left + right) // 2
            # 如果目标值与划分区间的元素相等时，直接返回
            if nums[mid] == target:
                return mid

            # 判断区间是否有序
            # 这里表示 [left, mid - 1] 是有序的
            if nums[0] <= nums[mid]:
                # target 落在 [left, mid - 1] 这个区间
                if nums[0] <= target < nums[mid]:
                    # 重新划分右边界
                    right = mid - 1
                # target 落在 [mid + 1, right] 这个区间
                else:
                    # 重新划分左边界
                    left = mid + 1
            
            # nums[0] > nums[mid] 时，表示 [mid + 1, right] 有序
            else:
                # target 落在 [mid + 1, right] 时
                if nums[mid] < target <= nums[right]:
                    # 重新划分左边界
                    left = mid + 1
                else:
                    # target 落在 [left, mid - 1] 这个区间
                    # 重新划分左边界
                    right = mid - 1

        return -1

实现结果

以上就是使用二分查找的思想，解决《33. 搜索旋转排序数组》问题的主要内容。