Search in Rotated Sorted Array
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
A sorted list was rotated at an unknown point (like [4,5,6,7,0,1,2]). Find the target in O(log n).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Compare the first value with the middle value. What does that tell you about which half is in order?
- Hint 2Once you know the ordered half, a simple range check tells you whether the target is in it.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A neatly sorted shelf of books 1 to 7 was cut in two, and the second part was placed in front: 4 5 6 7 | 1 2 3. Open the shelf in the middle. One side of your finger is always in neat order. Is your book within that neat side's range? Then search there. If not, it must be on the messy side, so search there instead.
- The obvious way
Linear scan: O(n).
- The key insight
At every step one side of the middle is in plain ascending order. If the first value is not bigger than the middle, the left side is the ordered one: if the target is within its range go left, else go right. Otherwise the right side is the ordered one and the same range test applies. Each step halves the search.
- The algorithm
- Markers at the two ends. Look at the middle: the target? Done.
- First value <= middle value? The left half is ordered.
- Left ordered: target between first and middle? Keep the left. Otherwise keep the right.
- Left not ordered: the right is. Target between middle and last? Keep the right. Otherwise keep the left.
Watch it run
Examplenumbers = [4, 5, 6, 7, 0, 1, 2], target = 0
Open in the middle: 7. The left side 4..7 is in order and 0 is not in that range, so go right.
range: [0, 1, 2]
Where people slip
- Use <= in nums[low] <= nums[middle]: with one item on the left it still counts as in order.
- With duplicates this idea can degrade to O(n).
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def search(nums, target):
low, high = 0, len(nums) - 1
while low <= high:
middle = (low + high) // 2
if nums[middle] == target:
return middle
if nums[low] <= nums[middle]: # left half is in order
if nums[low] <= target < nums[middle]:
high = middle - 1
else:
low = middle + 1
else: # right half is in order
if nums[middle] < target <= nums[high]:
low = middle + 1
else:
high = middle - 1
return -1Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.