LeetCode_Search in Rotated Sorted Array

Posted on | In | Views:

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).
（在时间复杂度为O(log n)的前提下在经旋转的有序数组中检索）

Example:



1. 二分查找

定义首尾指针，在每次循环的过程中将 target 和 首尾指针的序列的中间值进行比较。其中在更新首尾指针的过程中需要讨论当前的[left, middle]数组是有序还是无序两种情况讨论。具体实现如下：

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
29
30
31
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        
        left = 0
        right = len(nums)-1

        while left <= right:
            middle = (left + right) // 2
            
            if target == nums[middle]:
                return middle
            
            if nums[left] <= nums[middle]:
                if target < nums[middle] and target >= nums[left]:
                    right = middle - 1
                else:
                    left = middle + 1
            else:
                if target > nums[middle] and target <= nums[right]:
                    left = middle + 1
                else:
                    right = middle - 1
    
        return -1