A bus schedule lists departure times as distinct numbers in increasing order, but the list was rotated: it starts somewhere in the middle and wraps around, like [40, 50, 60, 10, 20, 30]. Write a function that returns the index of target, or -1 if it isn't there, in O(log n) time.
The list might not be rotated at all, and it might be empty.
40 ≤ 60, so the left half is sorted. 20 isn't between 40 and 60: search the right.
Write find_in_rotated(times, target) in Python or findInRotated(times, target) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 26 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Plain binary search breaks
In [40, 50, 60, 10, 20, 30], the middle is 60. The target 20 is smaller, but it's to the right. Comparing with the middle alone isn't enough anymore.
Step 2
One half is always in order
Split at mid. At least one side, [low..mid] or [mid..high], has no wrap-around in it, so it's sorted. You can tell which: if times[low] <= times[mid], the left side is sorted; otherwise the right side is.
Step 3
Is the target in the sorted half?
For a sorted half you can check containment with its two ends. If the left half is sorted and times[low] <= target < times[mid], search left; otherwise search right. If the right half is sorted and times[mid] < target <= times[high], search right; otherwise search left.
Step 4
Same loop as before
Everything else stays standard binary search: an inclusive range, mid + 1 / mid - 1, and -1 when the range runs out.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Binary search on [low, high]. On each step, return mid if it matches. Otherwise find the sorted half, check whether the target lies within its ends, and keep that half or the other one accordingly.
python
1def find_in_rotated(times, target):
2 low, high = 0, len(times) - 1
3 while low <= high:
4 mid = (low + high) // 2
5 if times[mid] == target:
6 return mid
7 if times[low] <= times[mid]: # left half is sorted
↑left half is in order
8 if times[low] <= target < times[mid]:
↑is the target inside it?
9 high = mid - 1
10 else:
11 low = mid + 1
12 else: # right half is sorted
13 if times[mid] < target <= times[high]:
↑otherwise the right half is in order
14 low = mid + 1
15 else:
16 high = mid - 1
17 return -1
javascript
1function findInRotated(times, target) {
2 let low = 0
3 let high = times.length - 1
4 while (low <= high) {
5 const mid = Math.floor((low + high) / 2)
6 if (times[mid] === target) return mid
7 if (times[low] <= times[mid]) { // left half is sorted
↑left half is in order
8 if (times[low] <= target && target < times[mid]) high = mid - 1