Minimum in a Sorted and Rotated Array

Given a sorted array of distinct elements arr[] of size n that is rotated at some unknown point, the task is to find the minimum element in it.

Input: arr[] = [5, 6, 1, 2, 3, 4]
Output: 1
Explanation: 1 is the minimum element present in the array.


Input: arr[] = [3, 1, 2]
Output: 1
Explanation: 1 is the minimum element present in the array.


Input: arr[] = [4, 2, 3]
Output: 2
Explanation: 2 is the only minimum element in the array.
Copy

public class Solution {

    public static int findMin(int[] arr) {
        return -1;
    }

    public static void main(String[] args) {

        int[] arr = {9, 10, 11, 12, 13, 1, 2, 3, 4, 5, 6, 7, 8};
        boolean test = true;

        test = test && findMin(arr) == 1;
        test = test && findMin(new int[]{5, 6, 1, 2, 3, 4}) == 1;

        test = test && findMin(new int[]{1, 2, 3, 4, 5, 6}) == 1; // No rotation, already sorted
        test = test && findMin(new int[]{2, 3, 4, 5, 6, 1}) == 1; // Rotated once


        // Single element (boundary case)
        test = test && findMin(new int[]{1}) == 1;

        // Two elements
        test = test && findMin(new int[]{2, 1}) == 1;
        test = test && findMin(new int[]{1, 2}) == 1;

        // Large input case
        test = test && findMin(new int[]{100, 200, 300, 400, 10, 20, 30}) == 10;

        // Case where rotation point is at the end
        test = test && findMin(new int[]{3, 4, 5, 6, 7, 8, 1}) == 1;

        // Duplicate values (edge case)
        test = test && findMin(new int[]{2, 2, 2, 3, 4, 1, 2}) == 1;

        // Large input with duplicates
        test = test && findMin(new int[]{10, 10, 10, 20, 30, 5, 10, 10}) == 5;

        if (test) {
            System.out.println("pass");
        } else {
            System.out.println("Fail");
        }
    }
}
Copy

Solution

 public static int findMin(int[] arr) {
        int low = 0, high = arr.length - 1, mid;

        while (low < high) {
            if (arr[low] < arr[high])
                return arr[low];

            mid = (low + high) / 2;

            if (arr[mid] > arr[high]) {
                low = mid + 1;
            } else if (arr[mid] < arr[high]) {
                high = mid;
            } else {
                high--;
            }
        }

        return arr[low];
}
Copy

Reference

• geeksforgeeks