Find Peak Element Using Binary Search in DSA C++

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 half to explore next.

Analogy: Imagine climbing a mountain range where you want to find a peak. Instead of walking the whole range, you look at the middle point. If the slope goes up to the right, you move right; if it goes up to the left, you move left. This way, you quickly find a peak without checking every step.

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

Dry Run Walkthrough

Input: array: [1, 3, 2, 5, 4, 6, 3]

Goal: Find any peak element index where element is greater than neighbors

Step 1: Calculate mid index as 3, value is 5

Array: 1 -> 3 -> 2 -> [5] -> 4 -> 6 -> 3
mid=3

Why: Start by checking middle element to decide which half to search next

Step 2: Compare mid value 5 with next element 4; since 5 > 4, move search to left half including mid

Search range: indices 0 to 3
Array: 1 -> 3 -> 2 -> [5]

Why: If mid is greater than next, peak must be on left side or at mid

Step 3: Calculate new mid index as 1, value is 3

Array: 1 -> [3] -> 2 -> 5
mid=1

Why: Check middle of left half to narrow down peak location

Step 4: Compare mid value 3 with next element 2; since 3 > 2, move search to left half including mid

Search range: indices 0 to 1
Array: 1 -> [3]

Why: Peak is on left side or at mid because mid is greater than next

Step 5: Calculate new mid index as 0, value is 1

Array: [1] -> 3
mid=0

Why: Check middle of new range to find peak

Step 6: Compare mid value 1 with next element 3; since 1 < 3, move search to right half excluding mid

Search range: indices 1 to 1
Array: [3]

Why: If mid is less than next, peak must be on right side

Step 7: Only one element left at index 1, which is 3; this is a peak

Peak found at index 1 with value 3

Why: Single element left is peak by definition

Result:

Peak element index: 1, value: 3

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int findPeakElement(const vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // Compare mid element with next element
            if (nums[mid] > nums[mid + 1]) {
                // Peak is in left half including mid
                right = mid;
            } else {
                // Peak is in right half excluding mid
                left = mid + 1;
            }
        }
        // left == right is peak index
        return left;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1, 3, 2, 5, 4, 6, 3};
    int peakIndex = sol.findPeakElement(nums);
    cout << "Peak element index: " << peakIndex << ", value: " << nums[peakIndex] << endl;
    return 0;
}

while (left < right) {

loop until search range narrows to one element

int mid = left + (right - left) / 2;

calculate middle index to check

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

if mid element is greater than next, peak is on left side including mid

right = mid;

move right boundary to mid to narrow search to left half

else { left = mid + 1; }

otherwise, move left boundary to mid+1 to search right half

return left;

return the index where left meets right, which is peak

Output

Peak element index: 1, value: 3

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 only one element exists

DSA C++

while (left < right) {

Strictly increasing array

Peak is last element because each next is bigger; binary search moves right

DSA C++

else { left = mid + 1; }

Strictly decreasing array

Peak is first element because each next is smaller; binary search moves left

DSA C++

if (nums[mid] > nums[mid + 1]) { right = mid; }

When to Use This Pattern

When you need to find a local maximum or peak in an array efficiently, use binary search by comparing mid element with its neighbor to decide search direction.

Common Mistakes

Mistake: Comparing mid element with previous instead of next element
Fix: Always compare mid with next element to decide which half contains a peak

Mistake: Using while (left <= right) causing infinite loop
Fix: Use while (left < right) to ensure loop ends when left meets right

Summary

Finds an index of a peak element where the element is greater than its neighbors.

Use when you want to quickly find a local maximum without checking every element.

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

Practice

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

easy

A. An element that is greater than its neighbors

B. An element that is smaller than its neighbors

C. The first element of the array

D. The last element of the array

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 only one side if at the boundary).

2. Step 2: Apply this to binary search context

   Binary search finds such an element by comparing mid element with neighbors to decide search direction.

3. Final Answer:

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

4. Quick Check:

   Peak element = greater than neighbors [OK]

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

Common Mistakes:

• Confusing peak with smallest element
• Thinking peak is always first or last element
• Ignoring boundary conditions

2. Which of the following is the correct syntax to start binary search for peak element in C++?

easy

A. int left = 1, right = n;

B. int left = 0, right = n;

C. int left = 0, right = n - 1;

D. int left = 1, right = n - 1;

Solution

1. Step 1: Identify valid index range for array of size n

   Array indices go from 0 to n-1, so left should start at 0 and right at n-1.

2. Step 2: Check each option for correct initialization

   int left = 0, right = n - 1; correctly initializes left=0 and right=n-1, suitable for binary search.

3. Final Answer:

   int left = 0, right = n - 1; -> Option C

4. Quick Check:

   Index range = 0 to n-1 [OK]

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

Common Mistakes:

• Starting left at 1 instead of 0
• Setting right to n instead of n-1
• Confusing inclusive and exclusive 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. 2

C. 3

D. 1

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 B

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 as peak incorrectly
• Confusing index with value
• Not checking both neighbors

4. Given the following code snippet, what is the bug that prevents finding the peak element correctly?

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

medium

A. Decreasing right by 1 skips potential peak

B. Mid calculation causes overflow

C. Loop condition should be left <= right

D. Returning left instead of right

Solution

1. Step 1: Analyze the binary search update steps

   If arr[mid] >= arr[mid+1], the code sets right = mid - 1, which skips mid as a candidate peak.

2. Step 2: Correct approach is to set right = mid to include mid in search

   Setting right = mid keeps mid in range; subtracting 1 may miss the peak.

3. Final Answer:

   Decreasing right by 1 skips potential peak -> Option A

4. Quick Check:

   Right update must keep mid included [OK]

Hint: Do not exclude mid when moving right pointer [OK]

Common Mistakes:

• Setting right = mid - 1 instead of right = mid
• Ignoring mid element as possible peak
• Incorrect loop condition

5. You have an array [10, 20, 15, 2, 23, 90, 67]. Using binary search for peak element, which index will be returned and why?

hard

A. 0, because 10 is the first element

B. 1, because 20 is a peak element

C. 6, because 67 is the last element

D. 5, because 90 is a peak element

Solution

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

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

2. Step 2: Binary search tends to find a peak, often the higher one

   Binary search will find 90 at index 5 because it is a higher peak than 20 at index 1.

3. Final Answer:

   5, because 90 is a peak element -> Option D

4. Quick Check:

   Highest peak found = index 5 [OK]

Hint: Binary search finds any peak; higher peaks likely found first [OK]

Common Mistakes:

• Assuming first peak is always returned
• Ignoring multiple peaks in array
• Confusing last element as peak without checking neighbors