Developers

Search in Rotated Sorted Array

MediumBinary searchGrade AAlso known as LeetCode 33

A list of distinct integers was sorted in increasing order, and then rotated: some number of items from the front were moved to the back without changing their order. For example [0, 1, 2, 4, 5, 6, 7] could become [4, 5, 6, 7, 0, 1, 2].

Given the rotated list and a target value, return the position of the target, or -1 if it is not in the list. Your solution must run in O(log n) time.

Examples

Input nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output 4
Input nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output -1
3 is not in the list.
Input nums = [1], target = 0
Output -1

Constraints

  • 1 <= nums.length <= 5,000
  • -10,000 <= nums[i] <= 10,000
  • All values are distinct.
  • The list is a rotation of an ascending sorted list.

Stuck? Take one hint at a time

Common mistakes
  • Using a strict less-than when comparing the left end with the middle, which breaks on two element ranges.
  • Checking the target against only one end of the sorted half.
  • Computing mid as (lo + hi) / 2 in languages where that can overflow.
  • Finding the rotation point with a scan, which makes the whole solution O(n).
Questions an interviewer may ask next
  • The list may contain duplicates. What breaks, and what is the worst case now?
  • Find the smallest element of the rotated list in O(log n).
  • Find how many times the list was rotated.
  • Return the position of the first occurrence when duplicates are allowed.

How often this is reported

Commonly reported across 14 of 25 tracked companies
14/25

Grade A: Reported in several independent candidate sources. This reflects what candidates report, not a guarantee of what any company will ask.