Search in Rotated Sorted Array

Problem Statement

LeetCode-33: 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 where 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]]

For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 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.

Approach

The problem is a variation of the binary search algorithm. The key idea is to find the pivot element and then perform a binary search on the correct half of the array.

Here is a high-level overview of the approach:

1. Find the pivot element using a modified binary search algorithm.
2. Perform a binary search on the correct half of the array.
3. Return the index of the target element if found, else return -1.

To find the pivot element, we can compare the middle element with the first element of the array to determine which half of the array is sorted. Based on this comparison, we can adjust the search space accordingly.

Implementation

Here is a Java implementation of the above approach:

public int search(int[] nums, int target) {
    int start = 0;
    int end = nums.length - 1;

    while(start <= end){
        int mid = start + (end-start)/2;
        if(nums[mid] == target){
                return mid;
        }
        //first half is sorted
        if(nums[start] <= nums[mid]){
            // if target is in the first half
            // adjust the end pointer
            if(nums[start] <= target && nums[mid] >= target){
                end = mid-1;
            }
            // else adjust the start pointer
            // to search in the second half
            else{
                start = mid+1;
            }
        }
        //second half is sorted
        else if(nums[mid] <= nums[end]){
            // if target is in the second half
            // adjust the start pointer
            if(nums[mid] <= target && nums[end] >= target){
                start = mid+1;
            }
            // else adjust the end pointer
            // to search in the first half
            else{
                end = mid-1;
            }
        }
    }
    return -1;
}

Complexity Analysis

The time complexity for this approach is $O(\log n)$ since we are performing binary search on the array. The space complexity is $O(1)$ since we are using a constant amount of extra space.