Search in Rotated Sorted Array Problem

Search in Rotated Sorted Array Problem — ExecCode Medium DSA Practice

Solve the Search in Rotated Sorted Array problem on ExecCode. Free online medium DSA practice in Binary Search. Write and run code in Java, C++, Python — no signup required to run.

Problem description

There is an integer array nums sorted in ascending order with distinct values. Before being passed to your function, nums is possibly rotated at an unknown pivot index k, so it becomes [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). Given the rotated array nums and an integer target, return the index of target if it is present in nums, or -1 if it is not. You must write an algorithm with O(log n) runtime complexity.

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. Input nums = [1], target = 0; Output -1

Constraints

1 ≤ nums.length ≤ 5000 -10⁴ ≤ nums[i] ≤ 10⁴ All values of nums are unique nums is an ascending array that is possibly rotated -10⁴ ≤ target ≤ 10⁴

Practice Search in Rotated Sorted Array free on ExecCode. Browse DSA problems, topic map, and placement guides.