Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

58. Search in Rotated Sorted Array

MediumDay 17 of 60Binary Search

A sorted array of distinct integers was rotated at some 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 a value target, return its index or -1 if it is absent. You must do it in O(log n).

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
Example 3
Input: nums = [1], target = 0
Output: -1
Constraints
  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i], target <= 10^4
  • All values are distinct
  • `nums` is a possibly rotated sorted array
Hints
Frequently asked at: Meta, Amazon, Microsoft, LinkedIn, Adobe
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min