Practice/Meta/Leetcode 33. Search in Rotated Sorted Array

Leetcode 33. Search in Rotated Sorted Array

CodingMust

Problem

You are given an integer array that was originally sorted in ascending order with distinct values. However, this array has been rotated at some unknown pivot index. For example, the array [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2] if rotated at pivot index 3.

Given this rotated array and a target integer value, write a function that returns the index position of the target value. If the target does not exist in the array, return -1.

Your solution must achieve O(log n) time complexity.

Requirements

1. Implement an efficient search that runs in logarithmic time
2. Handle the case where the target value does not exist in the array
3. Work correctly regardless of where the rotation occurred
4. Return the correct zero-based index of the target value

Constraints

• 1 ≤ nums.length ≤ 5000
• -10^4 ≤ nums[i] ≤ 10^4
• All values in nums are unique
• nums is guaranteed to be rotated at some pivot
• -10^4 ≤ target ≤ 10^4
• Must achieve O(log n) time complexity
• Should use O(1) extra space

Examples

Example 1:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 Output: 4 Explanation: The target value 0 is located at index 4

Example 2:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3 Output: -1 Explanation: The value 3 does not exist in the array

Example 3:

Input: nums = [1], target = 0 Output: -1 Explanation: Single element array does not contain the target

Example 4:

Input: nums = [5, 1, 3], target = 3 Output: 2 Explanation: The target value 3 is at index 2