📘

Search in Rotated Sorted Array

Given a rotated sorted array nums (with distinct values) and a target, return the index of target or -1 if not found.

You must achieve O(log n) time complexity.

Input:

4,5,6,7,0,1,2
0

Output:

Reasoning:

The given array is rotated, so we need to find the pivot point where the rotation occurred.
We use a modified binary search algorithm to achieve O(log n) time complexity, dividing the search space in half at each step.
The target value $0$ is less than the middle element of the array, so we repeat the search in the right half of the array: $[0, 1, 2]$ .
Since $0$ is found at the first position of the right half, which is the $4^{th}$ index in the original array (using 0-based indexing), the function returns $\boxed{4}$ .

Editor

Python 3.13.1

0/0

Run code to see test results.