Search in Rotated Sorted Array

You are tasked with finding a specific target value within a sorted array that has been rotated at an unknown pivot point. This is a common problem that tests your ability to adapt binary search for non-standard sorted data structures, a valuable skill in many algorithms and data processing scenarios.

Problem Description

Given an integer array nums that is sorted in ascending order and then possibly rotated at an unknown pivot index k (0 <= k < length of nums), such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]. You are also given an integer target.

Your goal is to implement a function that searches for target in nums. If target is found, return its index; otherwise, return -1.

Key Requirements:

• The algorithm must have a time complexity of O(log n), where n is the number of elements in the array.
• You must not use any built-in binary search functions.

Expected Behavior:

• If the target exists in the array, return the index of the target.
• If the target does not exist in the array, return -1.

Edge Cases to Consider:

• Empty array.
• Array with only one element.
• Array not rotated (pivot is 0).
• Target is the smallest or largest element.
• Target is present at the pivot point.

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1], target = 0
Output: -1
Explanation: The array has only one element, and the target is not present.

Example 4:

Input: nums = [1,3], target = 3
Output: 1
Explanation: The array is not rotated, and the target is found at index 1.

Constraints

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is guaranteed to be sorted and then rotated.
• -10^4 <= target <= 10^4

Notes

This problem is a variation of the standard binary search. The key challenge lies in determining which half of the array (left or right of the midpoint) is sorted and whether the target could lie within that sorted portion. You'll need to carefully analyze the relationship between the midpoint element, the start element, and the target to make informed decisions about where to continue your search.