LeetCode-33 搜索旋转排序数组

发表于 | 分类于 | 评论数： | 阅读次数：

题目：搜索旋转排序数组

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

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

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

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

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

示例 1:

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

示例 2:

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

思路

这题其实还是得使用二分法，但由于数组并不是完全有序的，所以得对二分法进行一定的修改。

  • 初始化low = 0, high = len(nums) - 1， mid = (low + high) // 2
  • 如果刚好target就是中间值，那就直接返回
  • 否则得继续查找，那么就只有两种情况：
    • 旋转点在右边，那么左边为有序数组，右边为无序数组
      • 若target在左边，那么high = mid - 1
      • 若target在右边，那么low = mid + 1
    • 旋转点在左边，那么左边为无序数组，右边为有序数组
      • 若target在右边，那么low = mid + 1
      • 若target在左边，那么high = mid - 1

注意：在判断范围的时候，需要判断边界。

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) - 1
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                return mid
            else:
                # 左边有序
                if nums[low] <= nums[mid]:
                    # target在左边
                    if nums[low] <= target < nums[mid]:
                        high = mid - 1
                    # target在右边
                    else:
                        low = mid + 1
                # 右边有序
                else:
                    # target在右边
                    if nums[mid] < target <= nums[high]:
                        low = mid + 1
                    else:
                        high = mid - 1
        return -1

如果大家有更好的方法，欢迎一起探讨。