mafeshsho8lmafeshsho8l
Get Started
All coding questions

Search in Rotated Sorted Array

medium
Blind 75NeetCode 150binary-searcharrays

Problem

Given an ascending array that has been rotated at an unknown pivot, find the index of a target value or return negative one. Achieve logarithmic time.

Examples

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Zero sits at index four after rotation.
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Three is not present.

Constraints

  • • 1 <= nums.length <= 5000
  • • All values are unique
  • • Array is a rotation of a sorted array
Hints(tap to reveal)
  • 1. One half around the midpoint is always sorted.
  • 2. Decide which half could contain the target.
Optimal approach(spoiler)
  1. Run a modified binary search tracking low, high, and mid.
  2. Determine which side of mid is sorted by comparing endpoints.
  3. If the target lies within the sorted side's range, search there.
  4. Otherwise search the other half.
  5. O(log n) time, O(1) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor