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

Search in Rotated Sorted Array

LeetCode #33Medium
One half is always sorted — use it to steer

Given an ascending sorted array that has been rotated at an unknown pivot, find the index of a target value in O(log n) time, returning -1 if it is not present.

Asked atAmazonMicrosoftMeta
step 1 / 13
sorted ↑
sorted ↑ (smaller)
4
5
6
7
0
1
2
[0][1][2][3][4][5][6]
Brute force · linear scan
▸
1given arr, target
2for i ← 0 to n − 1:
3    if arr[i] == target: return i
4return −1
state
  • target0

line 1A sorted array was ROTATED: [0,1,2,4,5,6,7] became [4,5,6,7,0,1,2]. Find 0. The cliff (7 → 0) seems to break binary search, so first instinct: linear scan.