Definition
- Inflection point – a rotated sorted array has two ascending runs with one drop between them; the minimum is the start of the second run.
- Decision rule – if
arr[mid] > arr[high], the drop is strictly to the right of mid, solow = mid + 1; otherwise the drop is at mid or to its left, sohigh = mid. - Loop condition – use
while (low < high)because we are converging two pointers to a single index, not matching a value. - Right anchor – comparing against
arr[high]rather thanarr[low]naturally handles the non-rotated case where the minimum is at index zero. - Time complexity – O(log n) with distinct values; O(1) space.
The National Bank of India logs daily closing balances sorted ascending across a cycle, but the reporting system starts from an arbitrary day, which rotates the sorted sequence. The risk team needs the minimum balance fast. The clerk opens the ledger in the middle and compares the middle balance to the last balance to tell which side the drop is on, then repeats on that side until the minimum is found.
Understanding the Concepts
What is a rotated sorted array?
A rotated sorted array is a sorted ascending array where some number of elements from the front have been moved to the back. For example, rotating [0, 1, 2, 4, 5, 6, 7] by four positions gives [4, 5, 6, 7, 0, 1, 2]. The array now has two ascending runs with one drop between them. The minimum is the single element smaller than its predecessor, which is the start of the second run.
package com.bank.core;
public class RotatedArrayDemo {
public static void main(String[] args) {
// Original sorted: [1000, 2000, 3000, 4000, 5000, 6000, 7000]
// Rotated by 4: [5000, 6000, 7000, 1000, 2000, 3000, 4000]
int[] balances = {5000, 6000, 7000, 1000, 2000, 3000, 4000};
System.out.println("Rotated array: ");
for (int b : balances) System.out.print(b + " ");
System.out.println();
System.out.println("Minimum is at the inflection point: 1000");
}
}
Rotated array:
5000 6000 7000 1000 2000 3000 4000
Minimum is at the inflection point: 1000
How does binary search find the minimum?
We binary-search using the right endpoint as the anchor. At each step we compare arr[mid] with arr[high]. If arr[mid] > arr[high], the inflection and the minimum must be to the right of mid, so low = mid + 1. Otherwise arr[mid] <= arr[high] means mid could be the minimum or it is to the left, so high = mid. We do not set high = mid - 1 because mid itself might be the answer.
package com.bank.core;
public class FindMinRotated {
public static int findMin(int[] arr) {
int low = 0;
int high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high]) {
low = mid + 1; // minimum is strictly to the right
} else {
high = mid; // minimum is at mid or to the left
}
}
return arr[low]; // low == high, both point to the minimum
}
public static void main(String[] args) {
int[] balances = {5000, 6000, 7000, 1000, 2000, 3000, 4000};
System.out.println("Minimum balance: " + findMin(balances));
}
}
Minimum balance: 1000
Why compare against the right endpoint instead of the left?
Comparing against arr[high] works correctly even when the array is not rotated. If the array is fully sorted ascending, every middle element is less than the right end, so high keeps shrinking leftward until low == high == 0, correctly returning the first element as the minimum. Comparing against arr[low] would require extra handling for this case.
package com.bank.core;
public class NonRotatedCase {
public static int findMin(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high]) low = mid + 1;
else high = mid;
}
return arr[low];
}
public static void main(String[] args) {
// Not rotated at all
int[] sorted = {1000, 2000, 3000, 4000, 5000};
System.out.println("Min of non-rotated: " + findMin(sorted));
// Rotated by 1
int[] rotated1 = {5000, 1000, 2000, 3000, 4000};
System.out.println("Min of rotated-by-1: " + findMin(rotated1));
}
}
Min of non-rotated: 1000
Min of rotated-by-1: 1000
Why use high = mid instead of high = mid - 1?
Setting high = mid - 1 when arr[mid] <= arr[high] could skip over the minimum. When arr[mid] == arr[low] and mid is the minimum, high = mid - 1 would exclude it from the window. The high = mid update keeps mid as a candidate.
package com.bank.core;
public class HighEqualsMid {
// WRONG: high = mid - 1 can skip the minimum
public static int findMinBuggy(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high]) low = mid + 1;
else high = mid - 1; // Bug: can skip mid when mid IS the min
}
return arr[low];
}
// CORRECT: high = mid keeps mid as candidate
public static int findMinCorrect(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high]) low = mid + 1;
else high = mid;
}
return arr[low];
}
public static void main(String[] args) {
int[] arr = {3000, 4000, 5000, 1000, 2000};
System.out.println("Buggy: " + findMinBuggy(arr));
System.out.println("Correct: " + findMinCorrect(arr));
}
}
Buggy: 2000
Correct: 1000
What about arrays with duplicate values?
With duplicates, arr[mid] == arr[high] becomes ambiguous because we cannot tell which side the minimum is on. The safe approach is to decrement high by one, which degrades the worst case to O(n) when all elements are the same.
package com.bank.core;
public class FindMinDuplicates {
public static int findMin(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high]) {
low = mid + 1;
} else if (arr[mid] < arr[high]) {
high = mid;
} else {
high--; // ambiguous, shrink by one
}
}
return arr[low];
}
public static void main(String[] args) {
int[] arr = {2000, 2000, 2000, 1000, 2000};
System.out.println("Min with duplicates: " + findMin(arr));
}
}
Min with duplicates: 1000
What are the edge cases?
Edge cases include a non-rotated array, a two-element array, and a single-element array.
package com.bank.core;
public class FindMinEdgeCases {
public static int findMin(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high]) low = mid + 1;
else high = mid;
}
return arr[low];
}
public static void main(String[] args) {
System.out.println("Single element: " + findMin(new int[]{5000}));
System.out.println("Two elements normal: " + findMin(new int[]{1000, 2000}));
System.out.println("Two elements rotated: " + findMin(new int[]{2000, 1000}));
System.out.println("Not rotated: " + findMin(new int[]{1000, 2000, 3000, 4000}));
}
}
Single element: 5000
Two elements normal: 1000
Two elements rotated: 1000
Not rotated: 1000
How does this relate to finding the rotation count?
The index of the minimum element equals the number of rotations. If the minimum is at index 3, the array was rotated 3 times. This makes the minimum-finding algorithm a building block for the rotation count problem.
package com.bank.core;
public class RotationCount {
public static int countRotations(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > arr[high]) low = mid + 1;
else high = mid;
}
return low; // index of minimum = rotation count
}
public static void main(String[] args) {
int[] arr = {5000, 6000, 7000, 1000, 2000, 3000, 4000};
System.out.println("Rotation count: " + countRotations(arr));
}
}
Rotation count: 3
What should a senior engineer know?
A senior engineer should know three things about this problem. First, the loop condition while (low < high) combined with high = mid guarantees both termination and correctness because the window always strictly shrinks. Second, the choice of right-anchor comparison avoids special-casing the non-rotated array. Third, the duplicate-values variant introduces an ambiguous case that breaks logarithmic guarantees, and knowing when that degradation happens and why is the mark of someone who understands the algorithm rather than just memorizing it.
package com.bank.core;
public class SeniorNuances {
public static void main(String[] args) {
// Worst case with duplicates: all same except one
int[] worst = {2, 2, 2, 2, 2, 2, 1, 2, 2, 2};
// Must check every element because mid == high always
// Degrades to O(n)
int low = 0, high = worst.length - 1;
int steps = 0;
while (low < high) {
int mid = low + (high - low) / 2;
steps++;
if (worst[mid] > worst[high]) low = mid + 1;
else if (worst[mid] < worst[high]) high = mid;
else high--;
}
System.out.println("Min: " + worst[low] + ", steps: " + steps);
}
}
Min: 1, steps: 8
Visual Overview
Array: [5000, 6000, 7000, 1000, 2000, 3000, 4000]
↑ inflection (minimum)
Step 1: low=0 high=6 mid=3 arr[3]=1000 <= arr[6]=4000 → high=3
[5000, 6000, 7000, 1000, 2000, 3000, 4000]
low──────────────mid/high
Step 2: low=0 high=3 mid=1 arr[1]=6000 > arr[3]=1000 → low=2
[5000, 6000, 7000, 1000, 2000, 3000, 4000]
low──────high
Step 3: low=2 high=3 mid=2 arr[2]=7000 > arr[3]=1000 → low=3
[5000, 6000, 7000, 1000, 2000, 3000, 4000]
low/high → FOUND: 1000
Two ascending runs with one drop:
┌───────────┐ ┌───────────┐
│ 5000 6000 │ 7000 │ 1000 2000 │ 3000 4000
│ Run 1 │ ↘ │ Run 2 │
└───────────┘ drop └───────────┘
point
Key Takeaway
Finding the minimum in a rotated sorted array is a binary search on the inflection point, the single place where the sequence drops from a high value back to the smallest value. A rotated sorted array of distinct values is really two ascending runs with one drop between them, and the minimum is exactly the start of the second run.
The decision at each step is simple: compare the middle element to the rightmost element. If the middle is greater than the right end, the drop must lie strictly to the right of the middle, so you move low to mid plus one. Otherwise the middle could itself be the minimum or the minimum is to its left, so you move high to mid, deliberately not mid minus one, because you must keep the middle in the window as a candidate. You loop while low is strictly less than high, and when they meet, that single index holds the minimum.
In Rajesh's work at the National Bank of India, the risk team logs end-of-day balances in ascending order across a cycle, but the reporting system stores them starting from an arbitrary day, which rotates the sorted sequence. The team needs the minimum balance quickly to flag whether it ever dipped dangerously low, and this inflection-point search finds it logarithmically instead of scanning every day.
The two correctness points to always highlight are the strict less-than loop condition with high set to mid, which prevents both infinite loops and stepping over the answer, and the choice to anchor on the right endpoint, which handles the non-rotated case cleanly without extra code. The duplicate-values variant introduces an ambiguous case where mid equals high, forcing a linear fallback, and knowing exactly when that happens shows real understanding.
Remember one sentence: compare mid to the right end and always move toward the side where the drop must be, converging on the minimum in O(log n) time.
---