Skip to main content
All Questions

Search in rotated sorted array

Medium

An array of distinct integers was sorted in ascending order and then rotated at an unknown pivot, so [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2].

Given the rotated array nums and an integer target, return the index of target in nums, or -1 if it isn't there. Your solution should run in O(log n) time.

Example 1

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 Output: 4

Example 2

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3 Output: -1

3 doesn't appear in nums.

Constraints

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i], target <= 10^4
  • All values in nums are distinct.

Related courses

Course

Machine Learning Engineer Interview Prep

Land your dream machine learning role at Meta, Google, Amazon, Apple, Microsoft, Nvidia, and other top companies. Learn from mock interviews, frameworks, and advice from senior candidates. Explore ML system design, core concepts, coding, behavioral interviews, and more.

Course

Data Science Interview Prep

Land your dream data science role at Google, Amazon, Microsoft, Meta, Apple, and other top companies. Learn from mock interviews, frameworks, and advice from senior candidates. Practice statistics, experimentation, coding, SQL, machine learning, behavioral interviews, and more.