Find Minimum in Rotated Sorted Array: Binary Search on Inflection

• Rotated sorted array – a sorted array shifted so it wraps around at one pivot point, creating two ascending runs.
• Minimum location – the minimum sits at the pivot, the single place where a larger element is immediately followed by a smaller one.
• Binary search on inflection – compare a[mid] to a[right]; if a[mid] > a[right], the pivot is to the right, otherwise at mid or to the left.
• O(log n) time, O(1) space – each iteration discards half the array.
• Duplicate handling – when a[mid] == a[right], shrink right by one to resolve ambiguity.

What is a rotated sorted array?

A sorted array rotated at some pivot has two sorted runs: a higher run at the front and a lower run at the back. The overall minimum sits at the very start of the back run, which is the pivot. For example, [4, 5, 6, 7, 0, 1, 2] is a sorted array [0, 1, 2, 4, 5, 6, 7] rotated by 4 positions, and the minimum is 0 at index 4.

Why use binary search instead of linear scan?

The naive approach scans for the one place where an element is greater than its next neighbor, which is O(n). Binary search finds the pivot in O(log n) time by always keeping the half that must contain it. For large datasets of rate checkpoints at the National Bank of India, this logarithmic search is essential.

How does the binary search work internally?

You keep a left and right index over the whole array. At each step you compute the mid index and compare a[mid] to a[right].

- If `a[mid] > a[right]`, the pivot must be strictly to the right of mid, because a sorted run would never have its middle larger than its end. Set `left = mid + 1`.
- Otherwise, `a[mid] <= a[right]`, meaning the run from mid to right is properly sorted and the minimum is at mid or to its left. Set `right = mid`.

You stop when left == right, and that index holds the minimum.

Array: [4, 5, 6, 7, 0, 1, 2]

Step 1: left=0, right=6, mid=3 → a[3]=7 > a[6]=2 → left=4
Step 2: left=4, right=6, mid=5 → a[5]=1 ≤ a[6]=2 → right=5
Step 3: left=4, right=5, mid=4 → a[4]=0 ≤ a[5]=1 → right=4
Step 4: left=4 == right=4 → answer is a[4] = 0

How do you implement it? (with code)

package com.bank.analysis;

import java.math.BigDecimal;

public class MinInRotatedArray {

    public static BigDecimal findMin(BigDecimal[] rates) {
        if (rates == null || rates.length == 0) {
            throw new IllegalArgumentException("Array must not be empty");
        }
        int lo = 0, hi = rates.length - 1;

        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (rates[mid].compareTo(rates[hi]) > 0) {
                lo = mid + 1;  // pivot is to the right
            } else {
                hi = mid;      // pivot is at mid or to the left
            }
        }
        return rates[lo];
    }

    public static void main(String[] args) {
        BigDecimal[] rates = {
            new BigDecimal("7.5"), new BigDecimal("8.0"),
            new BigDecimal("8.5"), new BigDecimal("3.0"),
            new BigDecimal("4.5"), new BigDecimal("6.0")
        };
        System.out.println("Minimum rate: " + findMin(rates));
    }
}

Minimum rate: 3.0

Why compare to the right boundary instead of the left?

Comparing to the right boundary rather than the left is deliberate and important. If you compared a[mid] to a[left] instead, a fully non-rotated array or certain rotations would be ambiguous and require extra cases. Comparing to a[right] cleanly decides which half holds the pivot in every rotation, including zero rotation where the array is already sorted and the answer is the first element.

// Comparing to right: works for all rotations including no rotation
if (rates[mid].compareTo(rates[hi]) > 0) lo = mid + 1;
else hi = mid;

// Comparing to left: fails for no rotation [1,2,3,4,5]
// a[mid]=3 > a[left]=1 is true, but minimum is at left, not right

How do you handle duplicates?

If the array can contain duplicate values, the comparison of mid to right can tie. When a[mid] == a[right], you cannot tell which half holds the minimum. You safely shrink the right boundary by one. This degrades the worst case to O(n) when the array is all equal values, which is unavoidable, but keeps it O(log n) on average.

public static BigDecimal findMinWithDuplicates(BigDecimal[] rates) {
    int lo = 0, hi = rates.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int cmp = rates[mid].compareTo(rates[hi]);
        if (cmp > 0) {
            lo = mid + 1;
        } else if (cmp < 0) {
            hi = mid;
        } else {
            hi--;  // cannot decide, shrink by one
        }
    }
    return rates[lo];
}

What are the edge cases?

• No rotation – the array is already sorted; a[mid] is always less than or equal to a[right], so right keeps moving left until left == right == 0, returning the first element.
• Single element – the loop does not execute; the single element is the minimum.
• Two elements – one comparison decides which is smaller.
• All equal elements – with duplicates handling, the right pointer shrinks one step at a time until convergence.

What about time and space complexity?

| Scenario | Time | Space |
|---|---|---|
| Distinct elements | O(log n) | O(1) |
| With duplicates (average) | O(log n) | O(1) |
| With duplicates (worst: all equal) | O(n) | O(1) |
| Linear scan (naive) | O(n) | O(1) |

What should a senior engineer know?

A senior engineer should know that mid = lo + (hi - lo) / 2 avoids integer overflow compared to (lo + hi) / 2. For financial rate values, always compare with BigDecimal.compareTo rather than primitive operators so exact decimal values are ordered correctly. The zero-rotation case is not a special case but falls naturally out of the compare-to-right logic.

What are common interview follow-up questions?

• What if there are duplicates? – Add the hi-- branch when mid equals right.
• Can you also find the index of the minimum? – Yes, return lo instead of rates[lo].
• What about searching for a target in a rotated array? – That is a separate problem (Search in Rotated Sorted Array) that uses the sorted-half detection technique.