Understanding Search in Rotated Sorted Array
Return the index of target in a rotated strictly increasing array, or -1 if it is absent.
How it works
At least one half is sorted, so its endpoint values decide whether the target can lie there.
Compare the midpoint with target. Identify which half is sorted. Keep that half only if its value range contains target.
Try an example
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
At least one half is sorted, so its endpoint values decide whether the target can lie there.
Constraints
- 0–64 distinct integers between -1,000,000 and 1,000,000.
- Input must be a rotation of a strictly increasing array; an unrotated array is allowed.
- Target is an integer between -1,000,000 and 1,000,000.
Use the simulator
Change the input, then choose Visualize input. Use Next and Previous to inspect each decision, or Play to advance automatically. Compare approaches and their complexity. Choose Try yourself to write JavaScript, select My code and Visualize code to inspect its execution, or Run Tests to check results.
Execution happens in your browser. Drafts are saved locally; avoid entering secrets or sensitive information.