0031 - Search in Rotated Sorted Array - revise

You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:

[3,4,5,6,1,2] if it was rotated 4 times. [1,2,3,4,5,6] if it was rotated 6 times. Given the rotated sorted array nums and an integer target, return the index of target within nums, or -1 if it is not present.

You may assume all elements in the sorted rotated array nums are unique,

A solution that runs in O(n) time is trivial, can you write an algorithm that runs in O(log n) time?

Example 1:

Input: nums = [3,4,5,6,1,2], target = 1

Output: 4 Example 2:

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

Output: -1

1. Core concept used - Binary Search
2. Find mid using left and right
3. if mid=target, return mid
4. If left<mid, then left side sorted. a. If left<=target<mid then set right=mid-1 b. else set left = mid+1
5. Else then right side is sorted. a. If mid<target<=right then set left=mid+1 b. else set right=mid-1
6. If we are out of loop then not found return -1

In [4]:

def search(nums, target):
    left,right=0,len(nums)-1
    while left<right:
        mid=left + (right-left)//2
        if nums[mid]==target:
            return mid
        if nums[left]<=nums[mid]:   #left side sorted
            if nums[left]<=target<nums[mid]:
                right=mid-1
            else:
                left=mid+1
        else:                       #right side sorted
            if nums[mid]<target<=nums[right]:
                left=mid+1
            else:
                right=mid-1
    return -1

In [8]:

search([3,4,5,6,1,2],1)

Out[8]:

4