33. Search in Rotated Sorted Array

Edited by Charles

Medium · Python · Array

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Use Binary Search.

Although the rotated array is not completely sorted, after splitting the current interval at mid, at least one half must be sorted.

Original study notes follow, including intermediate snippets and earlier attempts.

Idea

Use Binary Search.

Although the rotated array is not completely sorted, after splitting the current interval at mid, at least one half must be sorted.

For example:

nums = [4, 5, 6, 7, 0, 1, 2]

If:

left = 0
mid = 3
right = 6

then:

[4, 5, 6, 7] | [0, 1, 2]
 ↑        ↑       ↑     ↑
left     mid     mid+1 right

The left half is sorted.

Therefore, in every iteration:

1. Determine which half is sorted.
2. Check whether target lies inside that sorted half.
3. Decide which half to continue searching.

Step 1: Check Whether Target Is Found

As in normal binary search:

if nums[mid] == target:
    return mid

Step 2: Determine Which Half Is Sorted

Left Half Is Sorted

If:

nums[left] <= nums[mid]

then the interval:

[left, mid]

is sorted.

For example:

[4, 5, 6, 7, 0, 1, 2]
 ↑        ↑
left     mid

Since:

4 <= 7

the left half:

[4, 5, 6, 7]

is sorted.

Why Use <= Instead of <?

We must use:

nums[left] <= nums[mid]

instead of:

nums[left] < nums[mid]

because left can be equal to mid.

For example:

nums = [3, 1]
target = 1

left = 0
right = 1
mid = 0

Now:

left == mid

and:

nums[left] == nums[mid] == 3

The interval [left, mid] contains only one element, so it is still sorted.

Therefore:

nums[left] <= nums[mid]

correctly identifies the left half as sorted.

Step 3: Check Whether Target Is Inside the Sorted Half

Case 1: Left Half Is Sorted

We know:

nums[left] <= nums[mid]

Now check whether target is inside this sorted interval:

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

If true:

right = mid - 1

Otherwise:

left = mid + 1

So:

Left half is sorted

nums[left] <= target < nums[mid]
        ↓
target is in the left half
        ↓
right = mid - 1

Otherwise
        ↓
target must be in 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.

Check whether target lies inside:

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

If true:

left = mid + 1

Otherwise:

right = mid - 1

So:

Right half is sorted

nums[mid] < target <= nums[right]
        ↓
target is in the right half
        ↓
left = mid + 1

Otherwise
        ↓
target must be in the left half
        ↓
right = mid - 1

Example

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

Round 1

index:  0  1  2  3  4  5  6
nums:   4  5  6  7  0  1  2
        ↑        ↑        ↑
       left     mid      right

We have:

nums[left] = 4
nums[mid] = 7

Since:

4 <= 7

the left half is sorted:

[4, 5, 6, 7]

Check whether target = 0 is inside:

4 <= 0 < 7

False.

Therefore, search the right half:

left = mid + 1

Now:

left = 4
right = 6

Round 2

index:  0  1  2  3  4  5  6
nums:   4  5  6  7  0  1  2
                    ↑  ↑  ↑
                   left mid right

Now:

nums[left] = 0
nums[mid] = 1

Since:

0 <= 1

the left half is sorted.

Check:

0 <= target < 1

For target = 0:

0 <= 0 < 1

True.

Therefore:

right = mid - 1

Now:

left = 4
right = 4

Round 3

nums[4] = 0

Therefore:

return 4

Binary Search Logic

The entire logic can be summarized as:

                 nums[mid] == target
                         ↓
                    return mid

               Which half is sorted?
                        / \
                       /   \
                    Left   Right
                     ↓       ↓
              Is target   Is target
              inside it?  inside it?
                 / \         / \
               Yes  No     Yes  No
                ↓    ↓      ↓    ↓
              Left Right  Right Left

The key idea is:

Find the sorted half first, then determine whether the target lies inside that sorted half.

Complexity

Time Complexity:

O(log n)

Each iteration eliminates half of the current search interval.

Space Complexity:

O(1)

Key Points

At least one half is sorted

After choosing mid, either:

[left, mid]

or:

[mid, right]

must be sorted.

Determine the sorted half first

if nums[left] <= nums[mid]:
    # left half is sorted
else:
    # right half is sorted

Then check whether target is inside it

Left sorted:

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

Right sorted:

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

Use <=

nums[left] <= nums[mid]

because when:

left == mid

the left interval contains one element and is still sorted.

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	September 8, 2026

Python solution

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

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

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

        return -1

---

Back to Bonus Array · All Algorithm notes