Definition
- Peak element – an element strictly greater than both its neighbors, with positions outside the array treated as negative infinity.
- Slope-based binary search – compare
arr[mid]witharr[mid + 1]to determine the slope direction at mid. - Climbing – if
arr[mid] < arr[mid + 1], a peak lies to the right, solow = mid + 1. - Descending – if
arr[mid] > arr[mid + 1], mid is a peak or a peak lies to the left, sohigh = mid. - Convergence – use
while (low < high); when the pointers meet, that index is a peak. O(log n) time, O(1) space.
The National Bank of India charts hourly trading volume, which rises and falls like hills. The operations team wants any local high point, an hour busier than its immediate neighbors. A clerk stands at the middle hour and looks right. If the next hour is busier, the clerk walks uphill to the right because a peak must lie that way. If it is quieter, the peak is at the clerk's feet or to the left.
Understanding the Concepts
What is a peak element?
A peak element is one that is strictly greater than its neighbors. The array boundaries are treated as negative infinity, which means the first element is a peak if it is greater than the second, and the last element is a peak if it is greater than the second-to-last. A peak is guaranteed to exist in any array where adjacent elements differ.
package com.bank.core;
public class PeakElementBasic {
public static int findPeak(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < arr[mid + 1]) {
low = mid + 1; // peak is to the right
} else {
high = mid; // peak is at mid or to the left
}
}
return low; // low == high, points to a peak
}
public static void main(String[] args) {
int[] volumes = {100, 300, 500, 400, 200, 600, 350};
int peakIdx = findPeak(volumes);
System.out.println("Peak at index " + peakIdx + ": " + volumes[peakIdx]);
}
}
Peak at index 2: 500
Why does binary search work on an unsorted array?
Binary search works here because the problem has a slope structure. At every midpoint we can determine the direction of the slope by comparing mid to its right neighbor. If the slope is ascending, a peak must exist further right because the array cannot keep climbing forever (the boundary is negative infinity). If the slope is descending, a peak must be at mid or to its left. This slope-based reasoning lets us halve the search space each step.
package com.bank.core;
public class SlopeReasoning {
public static void main(String[] args) {
int[] arr = {100, 300, 500, 400, 200, 600, 350};
// ↑ascending ↓descending ↑asc ↓desc
// At mid=3 (400), arr[3]=400 > arr[4]=200 → descending → peak at 3 or left
// At mid=1 (300), arr[1]=300 < arr[2]=500 → ascending → peak at 2 or right
System.out.println("Slope at index 3: " + (arr[3] > arr[4] ? "descending" : "ascending"));
System.out.println("Slope at index 1: " + (arr[1] > arr[2] ? "descending" : "ascending"));
}
}
Slope at index 3: descending
Slope at index 1: ascending
How is the loop different from classic binary search?
Classic binary search uses while (low <= high) and searches for an exact value. Peak finding uses while (low < high) because we are converging two pointers to a single index rather than matching a value. The loop invariant is that a peak always exists within [low, high]. When low == high, that single index is the peak.
package com.bank.core;
public class LoopDifference {
public static int findPeak(int[] arr) {
int low = 0, high = arr.length - 1;
int steps = 0;
while (low < high) { // strict <, not <=
int mid = low + (high - low) / 2;
steps++;
if (arr[mid] < arr[mid + 1]) {
low = mid + 1;
} else {
high = mid; // mid stays as candidate
}
}
System.out.println("Converged in " + steps + " steps");
return low;
}
public static void main(String[] args) {
int[] arr = {100, 300, 500, 700, 600, 400, 200};
int idx = findPeak(arr);
System.out.println("Peak at index " + idx + ": " + arr[idx]);
}
}
Converged in 2 steps
Peak at index 3: 700
Why is mid + 1 always safe to read?
Inside the loop, low < high guarantees mid < high, which means mid + 1 <= high and is within bounds. This is a subtle but important correctness detail that candidates often overlook.
package com.bank.core;
public class MidPlusOneSafety {
public static void main(String[] args) {
int[] arr = {100, 500, 300};
int low = 0, high = 2;
// Step 1: low=0, high=2, mid=1
// mid+1 = 2 <= high = 2 → safe
int mid = low + (high - low) / 2;
System.out.println("mid=" + mid + ", mid+1=" + (mid + 1) + ", high=" + high);
System.out.println("arr[mid]=" + arr[mid] + ", arr[mid+1]=" + arr[mid + 1]);
// After: arr[1]=500 > arr[2]=300 → high=1
// Now low=0, high=1, mid=0, mid+1=1 → still safe
high = mid;
mid = low + (high - low) / 2;
System.out.println("mid=" + mid + ", mid+1=" + (mid + 1) + ", high=" + high);
}
}
mid=1, mid+1=2, high=2
arr[mid]=500, arr[mid+1]=300
mid=0, mid+1=1, high=1
What are common mistakes?
A common mistake is comparing mid with mid minus one instead of mid plus one, then using low <= high which risks accessing index minus one. Another mistake is returning arr[low] instead of low when the problem asks for the index.
package com.bank.core;
public class PeakMistakes {
// WRONG: using mid-1 can access index -1
// public static int findPeakBuggy(int[] arr) {
// int low = 0, high = arr.length - 1;
// while (low <= high) {
// int mid = low + (high - low) / 2;
// if (arr[mid] > arr[mid - 1]) { // IndexOutOfBoundsException when mid=0
// low = mid + 1;
// } else {
// high = mid - 1;
// }
// }
// return high;
// }
// CORRECT: compare mid with mid+1, use low < high
public static int findPeakCorrect(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < arr[mid + 1]) low = mid + 1;
else high = mid;
}
return low;
}
public static void main(String[] args) {
int[] arr = {500, 300, 100};
System.out.println("Peak index: " + findPeakCorrect(arr));
}
}
Peak index: 0
What are the edge cases?
Edge cases include a single-element array (always a peak), a two-element array, a strictly ascending array (last element is peak), and a strictly descending array (first element is peak).
package com.bank.core;
public class PeakEdgeCases {
public static int findPeak(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < arr[mid + 1]) low = mid + 1;
else high = mid;
}
return low;
}
public static void main(String[] args) {
System.out.println("Single: " + findPeak(new int[]{500}));
System.out.println("Two asc: " + findPeak(new int[]{100, 500}));
System.out.println("Two desc: " + findPeak(new int[]{500, 100}));
System.out.println("All ascending: " + findPeak(new int[]{100, 200, 300, 400, 500}));
System.out.println("All descending: " + findPeak(new int[]{500, 400, 300, 200, 100}));
}
}
Single: 0
Two asc: 1
Two desc: 0
All ascending: 4
All descending: 0
How does this relate to the bitonic array maximum problem?
A bitonic array that strictly increases then strictly decreases is a special case where there is exactly one peak. The peak-finding algorithm works identically on bitonic arrays. The difference is that a general array may have multiple peaks and we return any one of them, while a bitonic array has a unique peak.
package com.bank.core;
public class BitonicVsGeneral {
public static int findPeak(int[] arr) {
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < arr[mid + 1]) low = mid + 1;
else high = mid;
}
return low;
}
public static void main(String[] args) {
// Bitonic: exactly one peak
int[] bitonic = {100, 300, 500, 700, 400, 200};
System.out.println("Bitonic peak: " + findPeak(bitonic));
// General: multiple peaks, returns any one
int[] general = {100, 500, 300, 700, 400, 600, 200};
System.out.println("General peak: " + findPeak(general));
}
}
Bitonic peak: 3
General peak: 3
What should a senior engineer know?
A senior engineer should understand the correctness invariant: there is always a peak within the current [low, high] window because at least one boundary of the window points uphill into it. Moving toward the taller neighbor preserves this invariant while halving the window, which is the formal proof of correctness. The only requirement is that adjacent elements differ, so there is always a definite slope direction.
package com.bank.core;
public class PeakInvariant {
public static void main(String[] args) {
int[] arr = {100, 300, 200, 500, 400};
int low = 0, high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
System.out.println("Window [" + low + "," + high + "] mid=" + mid
+ " arr[mid]=" + arr[mid] + " arr[mid+1]=" + arr[mid + 1]);
if (arr[mid] < arr[mid + 1]) {
System.out.println(" Climbing → peak exists in [" + (mid + 1) + "," + high + "]");
low = mid + 1;
} else {
System.out.println(" Descending → peak exists in [" + low + "," + mid + "]");
high = mid;
}
}
System.out.println("Peak at index " + low + ": " + arr[low]);
}
}
Window [0,4] mid=2 arr[mid]=200 arr[mid+1]=500 Climbing → peak exists in [3,4] Window [3,4] mid=3 arr[mid]=500 arr[mid+1]=400 Descending → peak exists in [3,3] Peak at index 3: 500
Visual Overview
Array: [100, 300, 500, 400, 200, 600, 350]
Visualized as terrain:
500 600
/ \ / \
300 400 200 350
/ \ / \
100 200 (end)
↑ ascending ↓ descending ↑ ascending ↓ descending
Binary search on slope:
┌──────────────────────────────────────────────┐
│ Step 1: low=0 high=6 mid=3 │
│ arr[3]=400 > arr[4]=200 → descending │
│ Peak at mid or left → high = 3 │
│ │
│ Step 2: low=0 high=3 mid=1 │
│ arr[1]=300 < arr[2]=500 → ascending │
│ Peak to right → low = 2 │
│ │
│ Step 3: low=2 high=3 mid=2 │
│ arr[2]=500 > arr[3]=400 → descending │
│ Peak at mid or left → high = 2 │
│ │
│ low == high == 2 → Peak found: 500 │
└──────────────────────────────────────────────┘
Key Takeaway
Finding a peak element is a surprising case where binary search works on an array that is not sorted at all, because the problem has a slope structure that can be exploited. On each step you compare the middle element to its immediate right neighbor. If the right neighbor is larger, you are climbing a slope, and since the array boundaries behave like negative infinity, that uphill direction must eventually turn into a peak, so you move low past the middle. If the right neighbor is smaller, then the middle is itself a peak or a peak lies to its left, so you move high to the middle.
Because you always walk toward the taller neighbor, the invariant that a peak exists somewhere inside the current window is preserved while the window halves each step, so the search converges on a peak in logarithmic time. The index mid plus one is always safe to read because the loop only runs while low is strictly less than high, which keeps the middle at least one step short of the right edge.
In Rajesh's work at the National Bank of India, the trading desk records hourly trade volumes across the day, and the monitoring dashboard flags local peak hours to investigate spikes. The volumes rise and fall unpredictably so the series is unsorted, yet this slope-based binary search finds a peak logarithmically, keeping the dashboard responsive even over long time series.
The insight to emphasize in interviews is the proof of correctness: there is always a peak within the window because at least one boundary points uphill into it, and moving toward the higher neighbor never destroys that guarantee. Being able to articulate the invariant rather than just reciting the code is what demonstrates real understanding.
Remember one sentence: compare mid to its right neighbor and always walk uphill, because a peak is guaranteed in the direction of the ascending slope.
---