Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Find Minimum in Rotated Sorted Array

LeetCode #153Medium
Compare mid to hi to find the cliff

An ascending sorted array of unique values was rotated at an unknown pivot. Return its minimum element in O(log n) time.

Asked atAmazonMicrosoftGoogle
step 1 / 5
high block
low block (holds min)
4
5
6
7
0
1
2
[0][1][2][3][4][5][6]
lo
▲
hi
▲
Binary search on the rotation
▸
1lo = 0, hi = n − 1
2while lo < hi:
3    mid = lo + (hi − lo) / 2
4    if arr[mid] > arr[hi]:   // cliff is to the right
5        lo = mid + 1
6    else:                    // min at mid or left
7        hi = mid
8return arr[lo]
state
  • lo0
  • hi6

line 1A sorted array was ROTATED: [0,1,2,4,5,6,7] became [4,5,6,7,0,1,2]. The minimum is the rotation point — the single "cliff" where 7 drops to 0. We never scan: keep a range [lo, hi] containing the cliff and halve it. Start lo = 0, hi = 6.