Sorted and Rotated Minimum

JavaView on GFG

Problem Overview

Find minimum in sorted and rotated array.

See our study guide for structured GFG and LeetCode practice.

Intuition

Find minimum in sorted and rotated array. Binary search.

Algorithm

1If arr[mid] > arr[right]: min is in right half. Else min is in left half (including mid).

Common Pitfalls

• Same as LC 153. O(log n). When no rotation: arr[0] is minimum. Handle duplicates carefully.

Sorted and Rotated Minimum.java

Java

// Approach: Binary search. Find the pivot; the element at pivot is the minimum.
// Time: O(log n) Space: O(1)
class Solution {
    public int findMin(int[] arr) {
        int i = 0;
        int j = arr.length - 1;
        int n = arr.length;

        while (i <= j) {
            int mid = (i + j) >> 1;
            int next = (mid + 1) % n;
            int prev = (mid + n - 1) % n;

            if (arr[mid] <= arr[next] && arr[prev] >= arr[mid])
                return arr[mid];
            else {
                if (arr[mid] < arr[j])
                    j = mid - 1;
                else
                    i = mid + 1;
            }
        }
        return -1;
    }
}

Was this solution helpful?