Search in Rotated Sorted Array - Binary Search Explained

Why it works

A rotation breaks the global ordering but never creates two unsorted halves - exactly one half of any window is still sorted. Testing the sorted half with ordinary range logic keeps the search space halving: O(log n), same as plain binary search.

The problem

An integer array of unique elements was sorted then rotated at an unknown pivot. Given the array and a target, return the index of the target or -1 if not present. Must be O(log n).

Hints

• At least one half of the array is always fully sorted after rotation.
• Compare nums[lo] with nums[mid] to determine which half is sorted.
• If the left half is sorted and target is in [nums[lo], nums[mid]), search left.
• Otherwise search right. Symmetric logic for right half sorted case.

Test cases

Reference starter code

def search(nums, target):
    # Determine which half is sorted, then decide where to search
    pass

print(search([4, 5, 6, 7, 0, 1, 2], 0))  # 4
print(search([4, 5, 6, 7, 0, 1, 2], 3))  # -1
print(search([1], 0))                      # -1

More challenges in this topic

Try it yourself

Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.