[Binary Search Standard] Rotated Array Search - Coding Problem

You are given an integer array nums that was originally sorted in ascending order with all distinct values. Before being provided to you, this array may have been cyclically shifted (rotated left) at an unknown pivot index k (where 1 ≤ k < nums.length), transforming it from [a₀, a₁, a₂, ..., aₙ₋₁] into [aₖ, aₖ₊₁, ..., aₙ₋₁, a₀, a₁, ..., aₖ₋₁].

For instance, the sorted array [0, 1, 2, 4, 5, 6, 7] when cyclically shifted by 3 positions becomes [4, 5, 6, 7, 0, 1, 2].

Given this potentially shifted array nums and an integer target, your task is to locate the target value within the array. If the target exists in nums, return its index; otherwise, return -1.

Critical Requirement: Your solution must achieve O(log n) time complexity, where n is the length of the array.

The value 0 is located at index 4 in the shifted array. The original sorted array [0,1,2,4,5,6,7] was rotated by 4 positions.

The value 3 does not exist anywhere in the array, so we return -1.

The array contains only one element (1), and the target (0) is not present.

For instance, the sorted array [0, 1, 2, 4, 5, 6, 7] when cyclically shifted by 3 positions becomes [4, 5, 6, 7, 0, 1, 2].

Critical Requirement: Your solution must achieve O(log n) time complexity, where n is the length of the array.

The value 0 is located at index 4 in the shifted array. The original sorted array [0,1,2,4,5,6,7] was rotated by 4 positions.

The value 3 does not exist anywhere in the array, so we return -1.

The array contains only one element (1), and the target (0) is not present.

Rotated Array Search

Hints

Rotated Array Search

Hints