Skip to content

Volume ITechnology

4.11.5 — Search in Rotated Sorted Array ​

LeetCode 33 · Medium · ★ Blind 75

The problem ​

A list of different numbers was sorted and then rotated, as in 4.11.4. You are given the rotated list nums and a number target. Return the position of target, or −1 if it is not there, in O(\log n) time.

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

The list has between 1 and 5,000 numbers, all different.

What the problem is really asking ​

In a normal sorted list, "the middle is smaller than the target" tells you to go right. Here that no longer works, because the list is not sorted as a whole. In [4, 5, 6, 7, 0, 1, 2], the middle is 7, which is bigger than the target 0, but the 0 is to the right.

So the real question is: after one look at the middle, how can you still be sure which half to throw away?

Here is the fact that unlocks it.

Cut the list at mid, and at least one of the two halves is always a clean, unbroken sorted run.

Why? The list has only one drop. A single drop can only sit in one of the two halves. The other half has no drop, so it is sorted.

And in a clean sorted half, you can tell whether the target is inside: it is inside exactly when it lies between that half's smallest and biggest numbers.

The brute force, and where it wastes work ​

Scan every number.

python
def search(nums, target):
    for i, x in enumerate(nums):
        if x == target:
            return i
    return -1

That is O(n), and the problem asks for O(\log n).

The waste in one sentence: it never uses the fact that one half of every cut is cleanly sorted, so one range check could rule that half in or out.

The idea ​

At every step:

  1. Look at nums[mid]. If it is the target, you are done.
  2. Work out which half is clean.
  3. Check whether the target falls inside the clean half's range.
  4. If it does, search that half. If not, search the other half.

Either way, half the range is thrown away, so it stays O(\log n).

How to tell which half is clean: compare nums[low] with nums[mid]. If nums[low] <= nums[mid], the numbers rise from low to mid with no break, so the left half is clean. Otherwise the drop is in the left half, so the right half is clean.

The <= matters. When the range is just one or two numbers, low and mid can be the same position. One number on its own counts as sorted, so the comparison must say "clean" when they are equal.

The solution ​

python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1                       # (1)

        while low <= high:                                 # (2)
            mid = low + (high - low) // 2

            if nums[mid] == target:                        # (3)
                return mid

            if nums[low] <= nums[mid]:                     # (4)
                if nums[low] <= target < nums[mid]:        # (5)
                    high = mid - 1
                else:
                    low = mid + 1
            else:                                          # (6)
                if nums[mid] < target <= nums[high]:       # (7)
                    low = mid + 1
                else:
                    high = mid - 1

        return -1                                          # (8)
ts
function search(nums: number[], target: number): number {
  let low = 0, high = nums.length - 1;                     // (1)

  while (low <= high) {                                    // (2)
    const mid = low + Math.floor((high - low) / 2);

    if (nums[mid] === target) return mid;                  // (3)

    if (nums[low] <= nums[mid]) {                          // (4)
      if (nums[low] <= target && target < nums[mid]) high = mid - 1;   // (5)
      else low = mid + 1;
    } else {                                               // (6)
      if (nums[mid] < target && target <= nums[high]) low = mid + 1;   // (7)
      else high = mid - 1;
    }
  }

  return -1;                                               // (8)
}

Line by line ​

(1) and (2) Shape A from 4.11.1. We are looking for an exact value, so high is the last real position and the loop runs while low <= high.

(3) Found it.

(4) Is the left half clean? If nums[low] <= nums[mid], the numbers from low to mid rise without a break.

(5) Is the target inside the clean left half? Its numbers run from nums[low] up to nums[mid]. The target is inside if nums[low] <= target < nums[mid]. The right end uses <, not <=, because line (3) already checked nums[mid] and it was not the target. If the target is inside, search left with high = mid - 1. If not, it can only be in the right half, so low = mid + 1.

Python allows a chained comparison like a <= x < b, which means "a <= x and x < b". TypeScript does not, so we write both parts with &&.

(6) Otherwise the right half is clean.

(7) Is the target inside the clean right half? Its numbers run from just above nums[mid] up to nums[high]. Again mid is left out, because it was already checked. If inside, search right. If not, search left.

Notice what happens when the target is not in the clean half. We search the other half, the one with the drop in it. That is safe. On the next step, that half is cut in two again, and one of its halves is clean. So the same rule keeps working, all the way down.

(8) The range emptied, so the target is not in the list.

Trace ​

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

Steplowhighmidnums[mid]Clean halfTarget inside it?Action
10637left, 4 ≤ 7, holds 4 to 70 is not in 4 to 7low = 4
24651left, 0 ≤ 1, holds 0 to 10 is in 0 up to (not incl.) 1high = 4
34440—foundreturn 4

Now target = 3.

Steplowhighmidnums[mid]Clean halfTarget inside it?Action
10637left, holds 4 to 7nolow = 4
24651left, holds 0 to 1nolow = 6
36662left (one number)nolow = 7
end76return −1

Complexity, derived ​

Time. Every step throws away at least half of the range, whichever branch runs. So there are about \log_2 n steps, each doing a few comparisons. That is O(\log n).

Space. Three numbers, so O(1).

Edge cases ​

  • One number. One step: either it is the target, or the range empties.
  • Not rotated. The left half is always clean, and this becomes a normal binary search.
  • The target is the first or last number. Found when the range narrows to it.
  • Two numbers, like [3, 1] with target 1. mid is 0. 3 is not the target. The left half (just 3) is clean, but 1 is not in it, so low becomes 1, and then 1 is found.

The two-step alternative ​

There is a version that is easier to get right under pressure.

  1. Find the drop with the code from 4.11.4. That is O(\log n).
  2. Decide which of the two runs could hold the target, by comparing it with the ends of the runs.
  3. Run a normal binary search on that run.

The same speed, as two simple pieces instead of one tricky one. If the four-branch version keeps going wrong in an interview, switch to this. Two correct binary searches are better than one confused one.

What repeated numbers do ​

Search in Rotated Sorted Array II allows repeated numbers. When nums[low] == nums[mid], you can no longer tell which half is clean. [3, 1, 3, 3, 3] and [3, 3, 3, 1, 3] look identical at that comparison, but the drop is in different halves.

The fallback is low += 1, which drops one repeated number. The worst case becomes O(n). As in 4.11.4, that cannot be avoided when repeats are allowed.

Variations you will meet ​

  • Find Minimum in Rotated Sorted Array. The previous page.
  • Search a value in a list that was rotated more than once. Rotating twice is still one rotation, so nothing changes.

The general lesson: when only part of the data is sorted, find the part that is, and ask whether the target can be inside it.

What the interviewer will push on ​

"Why is one half always sorted?" There is exactly one drop, and it can only be in one half.

"How do you tell which half is clean?" nums[low] <= nums[mid]. The <= covers the case where low and mid are the same position.

"Why do your range checks leave out mid?" It was already checked and was not the target.

"Can you do it in two steps instead?" Yes. Find the drop, then search the right run. Same speed, easier to write.

"What if numbers can repeat?" On a tie, low += 1, and the worst case becomes linear.

One thing to volunteer: say the key fact before you write code. "One half is always cleanly sorted, so I check whether the target is in that half's range. If not, I search the other half." This whole problem is that sentence.

Next: 4.11.6 Time Based Key-Value Store. Binary search inside a design problem, looking for the largest value that does not go past a target.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet