Skip to main content

Search in Rotated Sorted Array

Question​

Given a sorted array of distinct integers that has been rotated by some number k in clockwise direction, find an element in the array in O(log n) time.

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

Solution​

all//Search in Rotated Sorted Array.py


def searchRotated(arr, target):
    start = 0
    end = len(arr) - 1
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return mid
        if arr[start] <= arr[mid]:
            if arr[start] <= target and target < arr[mid]:
                end = mid - 1
            else:
                start = mid + 1
        else:
            if arr[mid] < target and target <= arr[end]:
                start = mid + 1
            else:
                end = mid - 1
    return -1

arr = [4,5,6,7,0,1,2]
target = 0

print(searchRotated(arr, target)) # Output: 4