Leetcode 33. Search in Rotated Sorted Array

发表于 | 分类于

问题描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

解题思路

要求对数复杂度，首先考虑二分查找。先用二分查找找到最小值，然后再根据target所在区间进行二分查找。

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
26
27
28
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        l = 0
        r = len(nums) - 1
        while l < r:
            m = (l + r) // 2
            if nums[m] > nums[r]:
                l = m+1
            else:
                r = m
        s = l
        l = 0
        r = len(nums) - 1
        if nums[s] <= target <= nums[r]:
            l = s
        else:
            r = s
        while(l <= r):
            m = (l + r) // 2
            if nums[m] == target:
                return m
            elif nums[m] > target:
                r = m - 1
            else:
                l = m + 1
        return -1

进阶

可以考虑只进行一次二分查找。通过比较mid和r确定pivot点的大概位置。如果m大于r，且 target 在l与m之间，重新在 (l, m-1) 查找，若不是，则在 (m+1, r) 之间查找。若m小于r，当 target 在m与r之间则在 (m+1, r) 内进行查找，否则在 (l, m-1) 内进行查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            elif nums[m] > nums[r]:
                if nums[l] <= target <= nums[m]:
                    r = m - 1
                else:
                    l = m + 1
            else:
                if nums[m] <= target <= nums[r]:
                    l = m + 1
                else:
                    r = m - 1
        return -1
        # Time: O(log(N))
        # Space: O(1)