Search in Rotated Sorted Array

Problem Statement

Given an integer array nums sorted in ascending order and rotated at some pivot, and an integer target, return the index of target if it is in nums, or -1 if it is not.

You must write an algorithm with O(log n) runtime complexity.

Approach

Modified binary search. Determine which half is sorted, then decide which half to search.

Complexity Analysis

Examples

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] <= 10^4
• ▸All values of nums are unique
• ▸nums is sorted and rotated at some pivot

Sign in to run your code...