Search in Rotated Sorted Array

Problem

There is an integer array nums sorted in ascending order (with distinct values). Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

Examples

The brute-force approach

Scan the array linearly until you find the target.

for i in range(len(nums)):
    if nums[i] == target:
        return i
return -1

O(n), visits every element. The problem guarantees distinct values and a rotated sorted array, which means binary search applies if you can figure out which half is sorted at each step.

Spotting the pattern

This is a Binary Search problem. The key question to ask yourself:

When I compute a midpoint in a rotated array, how do I know which half to search next?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.