Search in Rotated Sorted Array

Search in Rotated Sorted Array Medium · Array, Binary Search · Facebook, Amazon, Microsoft, Bloomberg · Hints: 1. Determine which half of the array is strictly increasing by comparing the middle element with the leftmost element.
2. Once the sorted half is identified, check whether target falls inside its bounds; if so, continue searching that half, else search the opposite half.
3. When duplicates may be present and nums[left] == nums[mid] == nums[right], shrink the search interval by moving left or right inward — this can degrade worst‑case runtime to O(n).

Suppose an array nums originally contained distinct integers arranged in ascending order. At some unknown pivot index, the array was rotated — a suffix was moved to the front while the relative order inside each part stayed the same. For example, after rotating [1,2,3,4,5] at pivot 2, the array becomes [3,4,5,1,2].

Given an integer target, return the index where target appears in nums. If the target does not exist, return -1.

Your solution must run in O(log n) time.

As a follow‑up question, consider what happens when the values in nums are not guaranteed to be unique. In that setting, the worst‑case time complexity can become O(n). Be prepared to explain why and to modify the algorithm accordingly.

Example 1:

Input: nums = [6,7,1,2,3,4,5], target = 2
Output: 3

Explanation: 2 sits at index 3. The original sorted sequence [1,2,3,4,5,6,7] was rotated between 7 and 1.

nums = [6, 7, 1, 2, 3, 4, 5]
target = 2

3

Example 2:

Input: nums = [11,13,15,17,2,5,7], target = 8
Output: -1

Explanation: 8 is not present in the array, so we return -1.

Example 3:

Input: nums = [5], target = 5
Output: 0

Constraints:

• 1 <= nums.length <= 2000
• -100,000 <= nums[i] <= 100,000
• All elements of nums are distinct for the primary problem.
• nums has been rotated at some pivot; a rotation of zero positions (i.e., the array remains fully sorted) is allowed.