DSA 450 Notes

Problem Statement

Given a sorted array that has been rotated at some pivot unknown to you beforehand, search for a target value. If found, return its index; otherwise, return -1.

Constraints:

Array was originally sorted in ascending order
Array is rotated at some pivot point
All elements are distinct

Example:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Explanation: 0 is found at index 4

Example 2:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Explanation: 3 is not in the array

Example 3:

Input: nums = [1], target = 0
Output: -1

Approach 1: Brute Force (Linear Search)

Intuition

Simply scan through all elements to find the target.

Algorithm

Traverse the array from index 0 to n-1
If current element equals target, return index
Return -1 if target not found

java

public class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n) - May need to check all elements
Space Complexity: O(1) - No extra space

Approach 2: Modified Binary Search (Optimal)

Intuition

Even though the array is rotated, at least one half is always sorted. We can determine which half is sorted and check if the target lies in that half.

Key Observations:

If nums[left] <= nums[mid], the left half is sorted
If nums[mid] <= nums[right], the right half is sorted
Check if target lies in the sorted half, adjust search accordingly

Algorithm

Initialize left = 0 and right = n-1
While left <= right:
- Calculate mid
- If nums[mid] == target, return mid
- Determine which half is sorted:
  - If left half is sorted (nums[left] <= nums[mid]):
    - If target is in range [nums[left], nums[mid]), search left
    - Else search right
  - Else right half is sorted:
    - If target is in range (nums[mid], nums[right]], search right
    - Else search left
Return -1 if not found

java

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

Dry Run Example

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

Step 1:
left=0, right=6, mid=3
nums[mid]=7, target=0, not equal
nums[left]=4 <= nums[mid]=7, left half sorted
target=0 not in [4, 7), so left = mid + 1 = 4

Step 2:
left=4, right=6, mid=5
nums[mid]=1, target=0, not equal
nums[left]=0 <= nums[mid]=1, left half sorted
target=0 in [0, 1), so right = mid - 1 = 4

Step 3:
left=4, right=4, mid=4
nums[mid]=0, target=0, FOUND!

Return 4

Complexity Analysis

Time Complexity: O(log n) - Binary search
Space Complexity: O(1) - Only using pointers

Approach 3: Find Pivot + Binary Search

Intuition

First find the rotation point (smallest element), then perform standard binary search on the appropriate half.

java

public class Solution {
    private int findPivot(int[] nums) {
        int left = 0, right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
    private int binarySearch(int[] nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
    
    public int search(int[] nums, int target) {
        if (nums.length == 0) return -1;
        
        int pivot = findPivot(nums);
        
        // If no rotation
        if (pivot == 0) {
            return binarySearch(nums, 0, nums.length - 1, target);
        }
        
        // Decide which half to search
        if (target >= nums[0]) {
            return binarySearch(nums, 0, pivot - 1, target);
        } else {
            return binarySearch(nums, pivot, nums.length - 1, target);
        }
    }
}

Handling Duplicates

When array contains duplicates, the worst case becomes O(n).

Key Takeaways

Key Insight: At least one half of the array is always sorted
Modified Binary Search: Check which half is sorted, then decide search direction
Pivot Point: The minimum element indicates the rotation point
Duplicates: Make the problem harder; worst case becomes O(n)
Edge Cases: Single element, no rotation, target at pivot
Common Pattern: This technique applies to many rotated array problems (find min, find peak, etc.)

Search in a rotated sorted array

Problem Statement

Approach 1: Brute Force (Linear Search)

Intuition

Algorithm

Complexity Analysis

Approach 2: Modified Binary Search (Optimal)

Intuition

Algorithm

Dry Run Example

Complexity Analysis

Approach 3: Find Pivot + Binary Search

Intuition

Handling Duplicates

Key Takeaways