Search in rotated array

Electrical Engineering
1

Search for a given number in a sorted array that has been rotated by some arbitrary number. Return -1 if the number does not exist. Assume that the array does not contain duplicates.

2

Solution

Python 3

def search(arr, l, h, key):
    if l > h:
        return -1
 
    mid = (l + h) // 2
    if arr[mid] == key:
        return mid

    if arr[l] <= arr[mid]:
 
        if key >= arr[l] and key <= arr[mid]:
            return search(arr, l, mid-1, key)
        return search(arr, mid + 1, h, key)
    if key >= arr[mid] and key <= arr[h]:
        return search(arr, mid + 1, h, key)
    return search(arr, l, mid-1, key)