Java: Search in Rotated Sorted Array

Thought Process

Binary Search is the key to solving this problem efficiently. Although the array is rotated, it is sure that one part of the array (left or right of the midpoint) is always sorted. Based on the sorted part, we can decide whether to search in the left or right half by comparing the target value with the range of the sorted portion. 

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

        while(start<=end){

            int mid = (start+end)/2;

            if(nums[mid]==target)
                return mid;
            
            // Crux: After rotation, one half will always be sorted

            // If Left half is sorted
            if(nums[start]<=nums[mid]){

                if(nums[start]<=target && target<nums[mid])
                    end = mid-1;
                else
                    start = mid+1;
            }
            else{

                if(nums[mid]<=target && target<=nums[end])
                    start = mid+1;
                else
                    end = mid-1;
            }
        }
        return -1;
    }
}

Code Complexity

Time Complexity: O(log n)

The algorithm uses binary search, which halves the search space at each step, resulting in a logarithmic time complexity.

Space Complexity: O(1)

The algorithm uses a constant amount of extra space, regardless of the input size.

Code copied!