Search In Rotated Sorted Array

MEDIUM✓ CHIP-TIMEDLC #33 — FULL STATEMENT

The briefingthe full drill, in my own words

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.

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.

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

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

The hintstake 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 boardthe 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 splitstwo 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-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED