Search in Rotated sorted array

33.Search in Rotated Sorted Array

Array

Binary Search

Divide and Conquer

Problem Statement:

Given a sorted array nums that is rotated at some pivot index and a target value, return the index of target if it exists in the array, else return -1. The array contains no duplicates.

Example:

Input:

nums = [4,5,6,7,0,1,2], target = 0

→

Output:

4

Array was rotated at pivot 3, target 0 is at index 4

Algorithm:

1. Use modified binary search
2. Find which half is sorted
3. Check if target lies in sorted half
4. Adjust search space accordingly

Complexity:

Time: O(log n) | Space: O(1)

Java Solution:

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

Python Solution:

def search(self, nums: List[int], target: int) -> int:
    start, end = 0, len(nums) - 1
    
    while start <= end:
        mid = start + (end - start) // 2
        
        # Found target
        if nums[mid] == target:
            return mid
        
        # Left half is sorted
        if nums[start] <= nums[mid]:
            # Check if target is in left sorted half
            if target < nums[mid] and target >= nums[start]:
                end = mid - 1
            else:
                start = mid + 1
                
        # Right half is sorted
        else:
            # Check if target is in right sorted half
            if target > nums[mid] and target <= nums[end]:
                start = mid + 1
            else:
                end = mid - 1
    
    return -1

C++ Solution:

int search(vector<int>& nums, int target) {
    int start = 0;
    int end = nums.size() - 1;
    
    while (start <= end) {
        int mid = start + (end - start)/2;
        
        // Found target
        if (nums[mid] == target) return mid;
        
        // Left half is sorted
        if (nums[start] <= nums[mid]) {
            // Check if target is in left sorted half
            if (target < nums[mid] && target >= nums[start])
                end = mid - 1;
            else
                start = mid + 1;
                
        // Right half is sorted
        } else {
            // Check if target is in right sorted half
            if (target > nums[mid] && target <= nums[end])
                start = mid + 1;
            else
                end = mid - 1;
        }
    }
    
    return -1;
}