Search in Rotated Sorted Array

Searching in a Rotated Sorted Array

Problem

You’re given a sorted array that has been rotated at some unknown index.
The task is to find the index of a target element. If it doesn’t exist, return -1.

Strategy

At first, this doesn’t look like a normal binary search problem because the array isn’t fully sorted.

But after looking closer, one thing stands out:

Even after rotation, at least one half of the array is always sorted.

So instead of trying to “fix” the array, I just:

Find the middle element
Check which half is sorted
See if the target lies in that half
Move in that direction

So it’s still binary search, just with an extra decision at each step.

Code

class Solution:
    def search(self, nums, target):
        left, right = 0, len(nums) - 1

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

            if nums[mid] == target:
                return mid

            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

Key Lines Explained

if nums[left] <= nums[mid]:
This tells us the left half is sorted.
nums[left] <= target < nums[mid]
If true, the target must be in the left half.
else:
If the left half isn’t sorted, the right half definitely is.
nums[mid] < target <= nums[right]
Checks if the target lies in the right half.

Why This Works

Even though the array is rotated, it still has structure.

At every step, one half is properly sorted.
Using that, we eliminate half the array each time, just like binary search.

Complexity

Time: O(log n)
Space: O(1)

Final Note

This problem looks confusing at first because the order is broken.

But once you stop expecting a fully sorted array and instead look for the sorted half, the logic becomes much clearer.

DEV Community