Problem: Search in Rotated Sorted Array

Problem Statement

There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k.

Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

Approach: Modified Binary Search

In a rotated array, at least one half (left or right) is always sorted.

1. Find Mid: mid = left + (right - left) / 2.
2. Left Half Sorted?: if (nums[left] <= nums[mid]):
   • If target is within the range [nums[left], nums[mid]), go left.
   • Else, go right.
3. Right Half Sorted?: Else:
   • If target is within the range (nums[mid], nums[right]], go right.
   • Else, go left.

Java Implementation

public int search(int[] nums, int target) {
    int start = 0, end = nums.length - 1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) return mid;
        
        if (nums[start] <= nums[mid]) { // Left half sorted
            if (target >= nums[start] && target < nums[mid]) end = mid - 1;
            else start = mid + 1;
        } else { // Right half sorted
            if (target > nums[mid] && target <= nums[end]) start = mid + 1;
            else end = mid - 1;
        }
    }
    return -1;
}

Complexity Analysis

• Time Complexity: $O(\log n)$.
• Space Complexity: $O(1)$.

Interview Tips

• Mention that this still achieves logarithmic time because we eliminate half the search space in each step.
• Be careful with the <= in nums[start] <= nums[mid] to handle arrays of size 2.