The problem gives us an array that was originally sorted in ascending order, but then rotated some number of times. For example:

[1, 2, 3, 4, 5, 6]

could become:

[3, 4, 5, 6, 1, 2]

We are also given a target value. Our task is to return the index of the target in the array. If the target is not present, we return -1.

The important requirement is that the solution should run in O(log n) time.

Why Normal Binary Search Does Not Directly Work

In a normal sorted array, binary search works because the entire array is ordered. At each step, we can compare the middle value with the target and decide whether to search the left half or the right half.

But in a rotated sorted array, the whole array is not fully sorted anymore.

For example:

nums = [3, 4, 5, 6, 1, 2]
target = 1

The array is split into two sorted sections:

[3, 4, 5, 6] and [1, 2]

So the key idea is this:

At any point in the search, at least one half of the array will always be sorted.

Core Idea

We still use binary search with two pointers:

left = 0
right = len(nums) - 1

Then we calculate the middle index:

mid = (left + right) // 2

If nums[mid] == target, we return mid.

Otherwise, we need to figure out which half is sorted.

Case 1: Left Half Is Sorted

If:

nums[left] <= nums[mid]

then the left half from left to mid is sorted.

Now we check whether the target lies inside this sorted range:

nums[left] <= target < nums[mid]

If it does, we search the left half:

right = mid - 1

Otherwise, we search the right half:

left = mid + 1

Case 2: Right Half Is Sorted

If the left half is not sorted, then the right half must be sorted.

Now we check whether the target lies inside the sorted right range:

nums[mid] < target <= nums[right]

If it does, we search the right half:

left = mid + 1

Otherwise, we search the left half:

right = mid - 1

Python Solution

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

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

            if nums[mid] == target:
                return mid
            
            # If mid is in the left sorted section
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1

            # If mid is in the right sorted section
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

Walkthrough

Take this example:

nums = [3, 4, 5, 6, 1, 2]
target = 1

Initial values:

left = 0
right = 5
mid = 2
nums[mid] = 5

The left half [3, 4, 5] is sorted, but the target 1 is not inside that range. So we move right:

left = mid + 1

Now:

left = 3
right = 5
mid = 4
nums[mid] = 1

We found the target, so we return:

4

Complexity Analysis

The algorithm eliminates half of the search space in every iteration, just like binary search.

Time complexity:

O(log n)

Space complexity:

O(1)

Final Thoughts

The main trick in this problem is realizing that even though the entire array is rotated, one side of the midpoint will always be sorted. Once we identify the sorted side, we can decide whether the target belongs there or not.

This allows us to keep the efficiency of binary search and solve the problem in O(log n) time.