Search In Rotated Sorted Array

MEDIUM✓ CHIP-TIMEDLC #33 — FULL STATEMENT ↗

The drill: A distinct-valued ascending array has been rotated at an unknown pivot; locate a target's index in that rotated array, or report -1 if it isn't there.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An originally ascending array of distinct values has been rotated at some unknown pivot, the same setup as finding its minimum, but this time a target value is handed over alongside it.

The job is to report the index where that target sits in the rotated array, or −1 if it never appears at all.

Even though the array as a whole isn't sorted anymore, any slice you look at still has at least one half that reads in strict ascending order — that's the leverage the drill is built around.

EX 01

nums = [9, 12, 15, 18, 2, 5, 7] · target = 5

→ 5

TARGET ON THE ROTATED (RIGHT) SIDE

EX 02

nums = [9, 12, 15, 18, 2, 5, 7] · target = 13

→ -1

VALUE NOT PRESENT AT ALL

EX 03

nums = [9, 12, 15, 18, 2, 5, 7] · target = 9

→ 0

TARGET AT THE ROTATION'S START

array holds up to a few thousand distinct values
array may be rotated by any amount, including not at all
target may or may not appear anywhere in the array
answer is a single index, or −1 when the target is absent

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Even after rotation, at least one half of any [lo, hi] window is still purely sorted — the trick is figuring out which half that is before deciding where to search.

HINT 2 THE STRUCTURE

Compare nums[lo] to nums[mid]: if nums[lo] <= nums[mid], the left half is the sorted one; otherwise the right half is. A plain range check then tells you if the target lives there.

HINT 3 ONE STEP FROM THE ANSWER

Binary-search as usual, but pick a direction using that sorted-half test instead of a plain target-vs-mid comparison — discard the half that can't contain the target.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE BROKEN HALFPATTERN · MODIFIED BINARY SEARCHnums = [9, 12, 15, 18, 2, 5, 7] · target = 2

STEP 1

Target 2 in the rotated array. At each window, one half is guaranteed sorted — test which, then decide where to look.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/search-in-rotated-sorted-array.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[lo] <= nums[mid]:
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1

TIME O(LOG N)SPACE O(1)PYTHON · RACE PACE · 18 LN

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        for i, v in enumerate(nums):
            if v == target:
                return i
        return -1

TIME O(N)SPACE O(1)PYTHON · TRAINING PACE · 6 LN

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[lo] <= nums[mid]) {
                if (nums[lo] <= target && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}

TIME O(LOG N)SPACE O(1)JAVA · RACE PACE · 25 LN

class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

TIME O(N)SPACE O(1)JAVA · TRAINING PACE · 10 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED