Interview challenge · medium · array, binary-search

Search in Rotated Sorted Array

The challenge

A sorted array of distinct integers was rotated at an unknown pivot (for example [0, 1, 2, 4, 5, 6, 7] became [4, 5, 6, 7, 0, 1, 2]). Given a target, return its index, or -1 if it is not there. It must run in O(log n).

Example

[4, 5, 6, 7, 0, 1, 2], target 0  ->   4
[4, 5, 6, 7, 0, 1, 2], target 3  ->  -1
[1], target 1                    ->   0

Idea: binary search, with one extra question at each step. When you cut a rotated array in half, at least one of the halves is sorted, and you can tell which by comparing its ends. If the target falls inside the sorted half, search there; otherwise search the other one. Time O(log n).

The solution

1# Search in Rotated Array - ayotl.dev
2def search(a, t):
3    lo, hi = 0, len(a) - 1
4    while lo <= hi:
5        mid = (lo + hi) // 2
6        if a[mid] == t:
7            return mid
8        # one half is always sorted
9        if a[lo] <= a[mid]:
10            if a[lo] <= t < a[mid]:
11                hi = mid - 1
12            else:
13                lo = mid + 1
14        else:
15            if a[mid] < t <= a[hi]:
16                lo = mid + 1
17            else:
18                hi = mid - 1
19    return -1
20
21
22nums = [4, 5, 6, 7, 0, 1, 2]
23print(search(nums, 0))
24print(search(nums, 3))
25print(search([1], 1))

$ python3 search_in_rotated_sorted_array.py

-1

The video

Watch on YouTube →