Problem
You are given a sorted array nums with distinct values, which might have been rotated at an unknown pivot.
Your task: find the index of a target number, or return -1 if it is not present.
The algorithm must run in O(log n) time.
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
Approach
Use modified binary search:
Initialize low = 0 and high = n-1.
While low <= high, find mid = (low + high) // 2.
If nums[mid] == target, return mid.
Determine which side is sorted:
If left side is sorted (nums[low] <= nums[mid]), check if target is in [low, mid].
Else, target must be in the right side.
Adjust low and high accordingly.
If target not found, return -1.
This works in O(log n) because each step eliminates half of the search space.
Python Code
class Solution:
def search(self, nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# Check if left half is sorted
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
# Right half is sorted
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
Output
4