Search in Rotated Sorted Array

Medium#33rotated array

A sorted array of distinct numbers was rotated: some numbers from its start moved to its end, keeping their order. Find the index of a target, or return −1 if it is not there, in O(log n) time. Our example: [12, 19, 25, 31, 36, 2, 5, 9] and 5 — the answer is 6.

33 Search in Rotated Sorted ArrayWalkthrough · 1×

Example: [12, 19, 25, 31, 36, 2, 5, 9]: 2..36 in order, rotated to start at 12. Find 5. The bracket marks the half that rises with no drop.

012119225331436526579lo
still in the rangerises with no dropmiddle, checked nowthrown awayfound

lo starts at the first index, 0

01/19
restart · back · play · step
Speed
1function search(nums, target):
2 lo = 0
3 hi = len(nums) - 1
4 while lo <= hi:
5 mid = floor((lo + hi) / 2)
6 if nums[mid] == target:
7 return mid
8 if nums[lo] <= nums[mid]: // lo..mid rises
9 if nums[lo] <= target < nums[mid]: hi = mid - 1
10 else: lo = mid + 1
11 else: // mid..hi rises
12 if nums[mid] < target <= nums[hi]: lo = mid + 1
13 else: hi = mid - 1
14 return -1
state
lo
0
hi
–
mid
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Cut a rotated array at mid, and at least one side rises with no drop. nums[lo] <= nums[mid] means the left side does; otherwise the right side does.
  2. A rising piece holds exactly the values between its ends, so one check tells whether the target can be in it. If yes, keep that half; if not, the target can only be in the other one.
  3. Either way half the range goes, as in plain binary search. Here the first step drops the left half 12..31, and the second finds 5 between 2 and 9.

Complexity

Time O(log n): every step halves the range. Memory O(1): three indices.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.