Search in a Rotated Sorted Array

Table of Contents +

This is a classic interview question. It looks scary at first. A sorted array got twisted around. Now you have to find a number in it fast. The interviewer is not testing if you can search. They want to see if you can still use binary search even when the array is not fully sorted anymore.

🔄 The Problem

You start with a sorted array. Then someone rotates it at some unknown point. Rotating means they cut the array at one spot and move the front part to the back. So [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2].

Now you get a target number. You have to return the index where it sits. If it is not there, return -1. And the interviewer wants it in O(log n) time.

Here is what that looks like:

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4


Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1

O(log n) means the time grows very slowly even when the array gets huge. Every step should throw away half of what is left. That is the hint pointing straight at binary search.

🧠 The Simple Idea First

The obvious way is to just walk through the whole array. Check every element one by one. If you find the target, return its index. If you reach the end, return -1.

That works and it is easy to write. But it looks at every element, so it is O(n) time. The interviewer clearly asked for O(log n). So this is the version you mention out loud, then say “but we can do better.” It shows you know the easy path exists. You are just choosing the smarter one.

🎯 The Modified Binary Search Way

Normal binary search needs a fully sorted array. Our array is rotated, so it is not fully sorted. But here is the key fact that saves us.

If you cut the rotated array at the middle, one half is always sorted. It is impossible for both halves to be broken at the same time. The rotation point sits in only one of the two halves. The other half stays in clean sorted order.

So the plan is simple. Find the middle. Figure out which half is the sorted one. Then check if the target falls inside that sorted half. If yes, search there. If no, search the other half. Either way you drop half the array each step. That gives you O(log n).

Let’s walk through [4, 5, 6, 7, 0, 1, 2] looking for 0.

  • left = 0, right = 6, so mid = 3. The value at mid is 7.
  • Is the left half sorted? Compare nums[left] with nums[mid]: 4 <= 7 is true. So the left side [4, 5, 6, 7] is sorted.
  • Is the target 0 inside that sorted range, between 4 and 7? No. So 0 cannot be on the left. Move left = mid + 1, now left = 4.
  • New range is [0, 1, 2]. mid = 5, value 1. Left half [0, 1] is sorted. Is 0 between 0 and 1? Yes. So move right = mid - 1, now right = 4.
  • Now left = 4, right = 4, mid = 4, value 0. That equals the target. Return 4.

See how each step cut the work in half? That is the whole idea.

Steps to search a rotated sorted array

Let’s write the steps down before any code.

  1. Set left = 0 and right = n - 1.
  2. While left <= right:
    • Find mid = left + (right - left) / 2.
    • If nums[mid] equals the target, return mid.
    • If nums[left] <= nums[mid], the left half is sorted.
      • If the target sits between nums[left] and nums[mid], move right = mid - 1. Otherwise move left = mid + 1.
    • Else the right half is sorted.
      • If the target sits between nums[mid] and nums[right], move left = mid + 1. Otherwise move right = mid - 1.
  3. If the loop ends, the target is not there, so return -1.

Use less-than-or-equal in the checks

When you test if the target is inside the sorted half, use <= on the boundary, not just <. The endpoints nums[left] and nums[right] are real values in the array. If you skip them with a strict less-than, you can miss the target sitting right on the edge.

Code to search a rotated sorted array

Now let’s see it in every language.

search_rotated.py
# returns the index of target, or -1 if not found
def search(nums, target):
    left = 0
    right = len(nums) - 1


    while left <= right:
        mid = left + (right - left) // 2


        if nums[mid] == target:
            return mid


        # is the left half sorted?
        if nums[left] <= nums[mid]:
            # is target inside the sorted left half?
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # the right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1


    return -1


def main():
    nums = [4, 5, 6, 7, 0, 1, 2]
    print("Index of 0:", search(nums, 0))
    print("Index of 3:", search(nums, 3))


if __name__ == "__main__":
    main()

The output of the above code will be:

Index of 0: 4
Index of 3: -1

⏱️ Time and Space Complexity

Approach Time Space
Linear scan (brute force) O(n) O(1)
Modified binary search O(log n) O(1)

Both ways use only a few variables, so both are O(1) extra space. The real difference is time. The linear scan checks every element, so it is O(n). The modified binary search throws away half the array each step, so it is O(log n). That is the answer the interviewer wants.

Say the key insight out loud

The one sentence the interviewer wants to hear is this: “After splitting at the middle, one half is always sorted.” Say it early. It tells the interviewer you understand why binary search still works on a rotated array, not just that you memorized the code.

🧩 Key Takeaways

  • ✅ A rotated sorted array still lets you use binary search, because one half is always sorted after you split at the middle.
  • ✅ At each step, find the sorted half, then check if the target lies inside it to decide which way to go.
  • ✅ Use <= on the boundary checks so you do not miss a target sitting on an endpoint.
  • ✅ Time is O(log n) and extra space is O(1).

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    After you split a rotated sorted array at the middle, what is always true?

    Why: The rotation point lives in only one half, so the other half is always in clean sorted order.

  2. 2

    Why is a plain linear scan a weaker answer for this problem?

    Why: The linear scan works but checks every element, so it is O(n). The interviewer asked for O(log n).

  3. 3

    Once you know which half is sorted, what do you check next?

    Why: If the target is inside the sorted half's range, you search there; otherwise you search the other half.

  4. 4

    What does the function return when the target is not in the array?

    Why: When the loop ends without a match, the target is not present, so the function returns -1.

Score: 0 / 4

🚀 What’s Next?

Now that you can search a twisted array, build on the same idea:

Once you really get “one half is always sorted,” a lot of rotated-array problems stop feeling scary.

Previous String Compression Next Find First and Last Position of a Target

Share & Connect

Share on LinkedIn