33. Search in Rotated Sorted Array

🧩 Problem: There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2]. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity.

Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -104 <= target <= 104

🔑 Key Idea:

👉 In rotated sorted array, one side is always sorted; use that sorted half to decide where target can exist.

✅ Solution:

// O(logn) // O(1)

class Solution {

public int search(int[] nums, int target) {

int low = 0, high = nums.length-1;

while(low<=high) {

int mid = low + (high-low)/2;

if(nums[mid]==target)

return mid;

// right array sorted

if(nums[mid] < nums[high]) {

if(target > nums[mid] && target<=nums[high])

low = mid+1;

else high = mid-1;

}

// left array sorted

else {

if(target>=nums[low] && target<nums[mid])

high = mid-1;

else low = mid+1;

}

}

return -1;

}

}