https://leetcode.com/problems/search-in-rotated-sorted-array/
Search in Rotated Sorted Array
Suppose a sorted array 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.
Code
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums:
return -1
left, right = 0, len(nums)-1
while left <= right:
mid = (left + right) / 2
if nums[mid] == target:
return mid
if nums[left] <=nums[mid]:
# left ok
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
# right ok
if nums[right] >= target > nums[mid]:
left = mid + 1
else:
right = mid - 1
return -1
Idea
It is a variant of binary search. You have `left`, `right` and `mid` three pointers. You only return exact index of `mid` if you find `nums[mid] == target`. Otherwises you return -1. To identify whether you need to search in `[left, mid-1]` or `[mid+1, right]`, you need to determine `nums[left] <= nums[mid]` (line 16). If it is True, that means `nums[left:mid]` is intact from rotation. If it is False, that means `nums[mid+1:right]` is intact by rotation. Then you determine you need to search in the intact part of the rotated part (line 18 and 24).
Reference: