Find Peak Element Using Binary Search in DSA Java

Mental Model

A peak element is one that is bigger than its neighbors. We use binary search to quickly find such an element by checking the middle and deciding which side to search next.

Analogy: Imagine standing on a hill and wanting to find the top point without walking the whole hill. You look around your current spot and decide which direction goes uphill, then move that way until you reach the peak.

Index: 0   1   2   3   4   5   6
Value: 1 -> 3 -> 20 -> 4 -> 1 -> 0 -> 5
                 ↑
             mid pointer

Dry Run Walkthrough

Input: array: [1, 3, 20, 4, 1, 0, 5]

Goal: Find any peak element index using binary search

Step 1: Calculate mid = (0 + 6) / 2 = 3; compare nums[3]=4 with nums[4]=1

Array: 1 -> 3 -> 20 -> [4↑] -> 1 -> 0 -> 5

Why: Check if mid element is greater than next to decide search direction

Step 2: Since nums[3]=4 > nums[4]=1, move search to left half: high = mid = 3

Search range indices: 0 -> 3

Why: Peak must be on left side or at mid because nums[mid] > nums[mid+1]

Step 3: Calculate mid = (0 + 3) / 2 = 1; compare nums[1]=3 with nums[2]=20

Array: 1 -> [3↑] -> 20 -> 4 -> 1 -> 0 -> 5

Why: Check mid element against next to decide direction

Step 4: Since nums[1]=3 < nums[2]=20, move search to right half: low = mid + 1 = 2

Search range indices: 2 -> 3

Why: Peak must be on right side because nums[mid] < nums[mid+1]

Step 5: Calculate mid = (2 + 3) / 2 = 2; compare nums[2]=20 with nums[3]=4

Array: 1 -> 3 -> [20↑] -> 4 -> 1 -> 0 -> 5

Why: Check if mid element is greater than next

Step 6: Since nums[2]=20 > nums[3]=4, move search to left half: high = mid = 2

Search range indices: 2 -> 2

Why: Peak must be at mid or left side

Step 7: Now low == high == 2, return index 2 as peak element

Peak found at index 2 with value 20

Why: Search narrowed to one element which is peak

Result:

Array: 1 -> 3 -> [20↑] -> 4 -> 1 -> 0 -> 5
Peak element index: 2, value: 20

Annotated Code

DSA Java

public class PeakElementFinder {
    public static int findPeakElement(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[mid + 1]) {
                high = mid; // move left because peak is at mid or left
            } else {
                low = mid + 1; // move right because peak is right side
            }
        }
        return low; // low == high is peak index
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 20, 4, 1, 0, 5};
        int peakIndex = findPeakElement(nums);
        System.out.println("Peak element index: " + peakIndex + ", value: " + nums[peakIndex]);
    }
}

int mid = low + (high - low) / 2;

Calculate middle index to check peak condition safely avoiding overflow

if (nums[mid] > nums[mid + 1]) {

Compare mid element with next to decide search direction

high = mid; // move left because peak is at mid or left

Narrow search to left half including mid

low = mid + 1; // move right because peak is right side

Narrow search to right half excluding mid

return low; // low == high is peak index

Return the index where search converges as peak

Output

Peak element index: 2, value: 20

Complexity Analysis

Time: O(log n) because binary search halves the search space each step

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear scan O(n), binary search is much faster for large arrays

Edge Cases

Single element array

Returns index 0 as peak since it's the only element

DSA Java

while (low < high) {

Strictly increasing array

Returns last index as peak because last element is greater than previous

DSA Java

low = mid + 1;

Strictly decreasing array

Returns first index as peak because first element is greater than next

DSA Java

high = mid;

When to Use This Pattern

When you need to find a local maximum quickly in an unsorted array, use binary search on neighbors to reduce search space efficiently.

Common Mistakes

Mistake: Comparing nums[mid] with nums[mid - 1] instead of nums[mid + 1]
Fix: Always compare nums[mid] with nums[mid + 1] to decide direction safely without index errors

Mistake: Using low <= high in while loop causing infinite loop
Fix: Use low < high to ensure loop ends when low meets high

Summary

Finds an index of a peak element where neighbors are smaller.

Use when you want to find a local maximum efficiently without scanning all elements.

The key insight is comparing mid element with its next neighbor to decide which half contains a peak.

Practice

1. What is a peak element in an array when using binary search to find it?

easy

A. The smallest element in the array

B. An element that is greater than its neighbors

C. The first element of the array

D. An element equal to its neighbors

Solution

1. Step 1: Understand the definition of a peak element

   A peak element is one that is strictly greater than its neighbors on both sides (or just one side if at the boundary).

2. Step 2: Relate to binary search usage

   Binary search finds such an element by comparing mid elements with neighbors to decide which half to search next.

3. Final Answer:

   An element that is greater than its neighbors -> Option B

4. Quick Check:

   Peak element = greater than neighbors [OK]

Hint: Peak element is bigger than neighbors, not smallest [OK]

Common Mistakes:

• Confusing peak with minimum element
• Thinking peak must be at array ends only
• Assuming peak equals neighbors

2. Which of the following is the correct way to start the binary search for a peak element in Java?

easy

A. int left = 0, right = arr.length;

B. int left = 1, right = arr.length;

C. int left = 0, right = arr.length - 1;

D. int left = 1, right = arr.length - 1;

Solution

1. Step 1: Identify valid index range for binary search

   Array indices in Java go from 0 to length-1, so left should be 0 and right should be arr.length - 1.

2. Step 2: Check options for correct initialization

   int left = 0, right = arr.length - 1; correctly sets left=0 and right=arr.length-1, which covers the whole array.

3. Final Answer:

   int left = 0, right = arr.length - 1; -> Option C

4. Quick Check:

   Index range = 0 to length-1 [OK]

Hint: Array indices start at 0, end at length-1 [OK]

Common Mistakes:

• Starting right at arr.length causes out-of-bounds
• Starting left at 1 skips first element
• Using invalid index ranges

3. What will be the output index of the peak element for the array [1, 3, 20, 4, 1, 0] using binary search peak finding?

medium

A. 0

B. 1

C. 3

D. 2

Solution

1. Step 1: Identify peak elements in the array

   Array: [1, 3, 20, 4, 1, 0]. 20 at index 2 is greater than neighbors 3 and 4, so it's a peak.

2. Step 2: Binary search will find index 2 as peak

   Binary search compares mid elements and moves left or right until it finds 20 at index 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Peak at index 2 = 20 [OK]

Hint: Peak is local max, here 20 at index 2 [OK]

Common Mistakes:

• Choosing first or last element incorrectly
• Confusing peak with global max
• Ignoring neighbors comparison

4. Given this code snippet to find a peak element, what is the error?

int mid = left + (right - left) / 2;
if (arr[mid] < arr[mid + 1]) {
    left = mid + 1;
} else {
    right = mid - 1;
}
return left;

medium

A. It may cause ArrayIndexOutOfBoundsException at arr[mid + 1]

B. It returns right instead of left

C. It uses wrong mid calculation causing infinite loop

D. It should compare arr[mid] with arr[mid - 1]

Solution

1. Step 1: Check boundary conditions for arr[mid + 1]

   If mid is at the last index, arr[mid + 1] access causes ArrayIndexOutOfBoundsException.

2. Step 2: Identify missing boundary check

   The code does not check if mid + 1 is within array bounds before accessing.

3. Final Answer:

   It may cause ArrayIndexOutOfBoundsException at arr[mid + 1] -> Option A

4. Quick Check:

   Accessing arr[mid+1] at end causes error [OK]

Hint: Check array bounds before accessing mid+1 [OK]

Common Mistakes:

• Ignoring array boundary checks
• Assuming mid+1 always valid
• Confusing left and right updates

5. You have an array [10, 20, 15, 2, 23, 90, 67]. Using binary search to find a peak element, which index will the algorithm return?

hard

A. 5

B. 6

C. 4

D. 1

Solution

1. Step 1: Identify all peak elements in the array

   Array: [10, 20, 15, 2, 23, 90, 67]. Peaks are 20 (index 1), 90 (index 5).

2. Step 2: Understand binary search behavior

   Binary search compares mid with neighbors and moves towards the side with higher neighbor. It will find 90 at index 5 as peak.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Peak found at index 5 = 90 [OK]

Hint: Binary search finds any peak, here index 5 with value 90 [OK]

Common Mistakes:

• Assuming only first peak is returned
• Confusing peak with global max
• Not tracing binary search steps carefully