Find Minimum in Rotated Sorted Array - Java Solution

1. Introduction

This post explores a fascinating array manipulation problem: finding the minimum element in a rotated sorted array. This problem is an excellent example of applying binary search in a slightly unconventional scenario to achieve O(log n) runtime complexity.

Problem

Given a sorted array nums of unique elements that has been rotated between 1 and n times, the task is to determine the minimum element of the array. The array rotation implies that the order of elements has been shifted, and we need to efficiently find the smallest element.

2. Solution Steps

1. Implement a binary search algorithm.

2. Determine the middle element of the array.

3. Compare the middle element with the end of the array to identify the sorted portion.

4. Narrow down the search to either the left or right half of the array based on where the minimum element could be.

5. Repeat the process until the smallest element is found.

6. Ensure the algorithm runs in O(log n) time.

3. Code Program

public class FindMinimumInRotatedSortedArray {
    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        System.out.println(findMin(nums)); // Test the function
    }

    // Function to find the minimum element in a rotated sorted array
    public static int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Invalid input");
        }

        int start = 0, end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] > nums[end]) {
                // The minimum is in the right half
                start = mid + 1;
            } else {
                // The minimum is in the left half
                end = mid;
            }
        }
        return nums[start]; // Start and end will converge to the minimum element
    }
}

Output:

0

Explanation:

1. findMin: This function implements a modified binary search to find the minimum element in a rotated sorted array.

2. It first checks for an empty or null array.

3. The function calculates the mid-point and compares the value at mid with the end of the array to determine the sorted part of the array.

4. Based on the comparison, the search space is narrowed to either the left or the right half of the array.

5. The process continues until the start and end pointers converge, at which point the smallest element is found.

6. This approach ensures that the minimum element is found in O(log n) time, exploiting the partially sorted nature of the array.