What is the brute force approach and complexity for Search in Rotated Sorted Array?

Check every index until target is found with time complexity O(N) and space complexity O(1).

What is the optimal approach and complexity for Search in Rotated Sorted Array?

At each mid, one half is sorted; go into it only if target fits its range with optimal time complexity O(log N) and space complexity O(1).

Search in Rotated Sorted Array

Q: How do you identify the pattern for Search in Rotated Sorted Array?

Look for key signals in the prompt: "sorted, then rotated" indicates Two sorted runs. At any split, one half is a clean sorted run.; "return the index of target" indicates Now there is a target (unlike Find Minimum), so we must decide which half can contain it.; "distinct values" indicates `nums[lo] <= nums[mid]` reliably tells which half is sorted. With duplicates (LC 81) it can't.; "O(log n)" indicates Linear scan is not allowed — binary search..

Medium·LeetCode #33 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given an array nums of distinct numbers. It was sorted from smallest to largest, and then possibly rotated: cut at some index k and the front part moved to the back. For example, [0, 1, 2, 4, 5, 6, 7] rotated at k = 3 becomes [4, 5, 6, 7, 0, 1, 2].

You are also given a number target. Return the index of target in nums, or -1 if it is not there. Your solution must run in O(log n) time.

Input

A rotated sorted array nums of distinct integers, and an integer target.

Output

The index of target in nums, or -1 if it is not present.

Example 1

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

Output: 4

0 sits at index 4, right after the drop from 7.

Example 2

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

Output: -1

3 is not in the array.

Example 3

Input: nums = [1], target = 0

Output: -1

The only element is 1.

Constraints

• 1 ≤ n ≤ 5000
• −10^4 ≤ nums[i] ≤ 10^4
• All values in nums are distinct.
• nums is a sorted array that may have been rotated.
• −10^4 ≤ target ≤ 10^4

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“sorted, then rotated”

→ Two sorted runs. At any split, one half is a clean sorted run.

“return the index of target”

→ Now there is a target (unlike Find Minimum), so we must decide which half can contain it.

“distinct values”

→ `nums[lo] <= nums[mid]` reliably tells which half is sorted. With duplicates (LC 81) it can't.

“O(log n)”

→ Linear scan is not allowed — binary search.

Approach Complexity Ladder

Brute Force — linear scanO(N)O(1)

Check every index until target is found

Better — find the pivot, then binary search one sideO(log N)O(1)

LC 153 finds the minimum's index; then a normal binary search on the right sorted piece

Optimal — one pass, check the sorted halfO(log N)O(1)

At each mid, one half is sorted; go into it only if target fits its range

Brute Force Intuition

Walk the array from left to right. Return the first index where nums[i] == target, or -1 at the end.

Recognition rule for this sub-pattern:

Array is not fully sorted, but one half always is. Decide which half is sorted, then which half holds the answer.

Remember this · Binary Search

Trigger

Sorted data, "minimum X such that…", "maximum X such that…", rotated arrays, answers that are monotonic (if X works, X+1 also works).

Think

Is there a yes/no question whose answers look like NNNNYYYY? Then binary search for the first Y.

Key question

What is my check function, and is it monotonic?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Binary Search translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Order Book Price Level Matching

std::lower_bound lookup in sorted price ticks for limit orders.

Explore Track

C++ Internals

CPU Branch Prediction & Cache Efficiency

Branch mispredictions in binary search and branchless mid-point arithmetic.

Explore Track

Find Minimum in Rotated Sorted Array Find Peak Element