Why?

I was solving a leetcode problem which states

Given a sorted array nums that is rotated at an unknown pivot, return the index of the target value if it exists in the array; otherwise, return -1. The solution must have a runtime complexity of O(log n).

I realized that the given array is a sorted array that has been rotated at an unknown pivot. This insight led me to consider using a modified binary search to achieve the required O(log n) runtime complexity. The main challenge is to determine which part of the array (left or right of the middle element) is sorted and then decide where to search for the target.

Approach

The solution uses a binary search approach with a slight modification to handle the rotated array:

1. Initialize Pointers: Start with two pointers, lo and hi, representing the start and end of the array, respectively.
2. Binary Search Loop: While lo is less than or equal to hi:
   • Calculate the middle index, mid.
   • Check if the middle element is the target. If yes, return its index.
   • Determine which part of the array is sorted:
     • If the left part (nums[lo] to nums[mid]) is sorted:
     • Check if the target lies within this range. If so, adjust hi to mid - 1.
     • Otherwise, adjust lo to mid + 1 to search in the unsorted right part.
     • If the right part (nums[mid] to nums[hi]) is sorted:
     • Check if the target lies within this range. If so, adjust lo to mid + 1.
     • Otherwise, adjust hi to mid - 1 to search in the unsorted left part.
3. Return the Result: If the target is not found, return -1.

Complexity

• Time Complexity: The time complexity is O(log n) because the binary search reduces the search space by half in each iteration.
• Space Complexity: The space complexity is O(1) since we are using only a few extra variables.

Code

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;

            if (nums[mid] == target) {
                return mid;
            }
            // Check if the left part is sorted
            if (nums[lo] <= nums[mid]) {
                if (nums[lo] <= target && target < nums[mid]) {
                    hi = mid - 1; 
                } else {
                    lo = mid + 1; 
                }
            } 
            // Otherwise, the right part must be sorted
            else {
                if (nums[mid] < target && target <= nums[hi]) {
                    lo = mid + 1; 
                } else {
                    hi = mid - 1; 
                }
            }
        }

        return -1;
    }
}

By using this approach, we efficiently find the target in a rotated sorted array with logarithmic time complexity, making it suitable for large datasets.