Leetcode: Search in Rotated Sorted Array

Search in Rotated Sorted Array



Similar Problems:


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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/search-in-rotated-sorted-array
## Basic Ideas: Binary search
##  Find the pivot. And do two binary search
## Complexity: Time O(log(n)), Space O(1)
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        length = len(nums)
        if length == 0: return -1
        left, right = 0, length - 1
        while left<right:
            mid = left + int((right-left)/2)
            # 5 6 7 0 1 2 3
            if nums[mid] < nums[right]:
                # check the left half(included)
                right = mid
            else:
                left = mid + 1

        pivot = left
        # binary search for part1
        left, right = 0, pivot-1
        while left<=right:
            mid = left + int((right-left)/2)
            if nums[mid] == target: return mid
            if nums[mid] < target: left = mid + 1
            else: right = mid - 1

        # binary search for part2
        left, right = pivot, length-1
        while left<=right:
            mid = left + int((right-left)/2)
            if nums[mid] == target: return mid
            if nums[mid] < target: left = mid + 1
            else: right = mid - 1

        return -1
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.