Coding interview problems › Binary Search

🔍 Binary Search Medium

Search in Rotated Sorted Array

Search in Rotated Sorted Array explained: one binary search that finds the sorted half at every step, O(log n). Tested Python, pitfalls and a live visual.

Also searched as: search in a rotated sorted array · binary search on rotated array · pivoted sorted array search

🔍

Try it live Free

Binary Search

Use the binary search lab to get the halving loop and its boundaries solid first; this problem is the same loop with one extra question per step: which half is sorted?

Open the playground →

The problem

A sorted list of distinct integers has been rotated at an unknown point, so [1, 2, 4, 6, 8] might become [6, 8, 1, 2, 4]. Given the rotated list and a target, return its index or -1, in O(log n) time.

Inputnums = [6, 8, 1, 2, 4], target = 2
Output3
Inputnums = [6, 8, 1, 2, 4], target = 7
Output-1

The key insight

Cut a rotated array anywhere and at least one half is still perfectly sorted. Compare nums[lo] with nums[mid] to find which half that is. For the sorted half you can tell instantly whether the target lies inside its range; if it does, search there, otherwise search the other half.

Brute force first: A linear scan finds the target in O(n), and finding the rotation point first then running two binary searches works but is more code to get right.

Step-by-step approach

  1. Use the inclusive binary search: lo = 0, hi = len(nums) - 1, loop while lo <= hi.
  2. Compute mid; if nums[mid] == target return mid.
  3. If nums[lo] <= nums[mid], the left half [lo, mid] is sorted. If nums[lo] <= target < nums[mid], move hi = mid - 1, else lo = mid + 1.
  4. Otherwise the right half [mid, hi] is sorted. If nums[mid] < target <= nums[hi], move lo = mid + 1, else hi = mid - 1.
  5. If the loop ends, return -1.

Python solution

PYTHON 3tested
def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:               # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                   # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Complexity

TimeO(log n)
SpaceO(1)

Each iteration does constant work and discards half of the remaining range, exactly like ordinary binary search.

Common mistakes

Frequently asked questions

What is the time and space complexity?

O(log n) time and O(1) extra space, because each step discards half of the search range.

What if the array contains duplicates?

When nums[lo], nums[mid] and nums[hi] are equal you cannot tell which half is sorted, so a common fix is to shrink the range with lo += 1 and hi -= 1. The worst case then becomes O(n).

Does the solution work if the array was not rotated at all?

Yes. An unrotated array has its left half sorted at every step, so the code behaves exactly like normal binary search.

How do I find the rotation point itself?

Binary search for the minimum element: compare nums[mid] with nums[hi] and move towards the unsorted side. That is the Find Minimum in Rotated Sorted Array problem.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Binary Search Binary Search lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.