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 side to search next.

Analogy: Imagine climbing a mountain range where you can only see the peak by looking at your current position and its neighbors. If the right neighbor is higher, you walk right; if the left neighbor is higher, you walk left. Eventually, you reach a 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 where the element is greater than its neighbors

Step 1: Calculate mid = (0 + 6) / 2 = 3, check element at index 3 (value 4)

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

Why: We start by checking the middle element to decide which half to search next

Step 2: Compare mid element 4 with its right neighbor 1; since 4 > 1, move search to left half including mid

Search range: indices 0 to 3
Array: 1 -> 3 -> 20 -> [4↑] -> 1 -> 0 -> 5

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

Step 3: Calculate mid = (0 + 3) / 2 = 1, check element at index 1 (value 3)

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

Why: Narrowing down to left half, check new mid element

Step 4: Compare mid element 3 with right neighbor 20; since 3 < 20, move search to right half excluding mid

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

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

Step 5: Calculate mid = (2 + 3) / 2 = 2, check element at index 2 (value 20)

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

Why: Check the new mid element in the narrowed range

Step 6: Compare mid element 20 with neighbors 3 (left) and 4 (right); 20 > 3 and 20 > 4, found peak

Peak element at index 2 with value 20

Why: Element is greater than both neighbors, so it is a peak

Result:

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

Annotated Code

DSA C

#include <stdio.h>

int findPeakElement(int* nums, int numsSize) {
    int left = 0, right = numsSize - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1]) {
            left = mid + 1;  // move right because peak is on right side
        } else {
            right = mid;     // move left because peak is on left side or mid
        }
    }
    return left; // left == right is peak index
}

int main() {
    int nums[] = {1, 3, 20, 4, 1, 0, 5};
    int size = sizeof(nums) / sizeof(nums[0]);
    int peakIndex = findPeakElement(nums, size);
    printf("Peak element index: %d, value: %d\n", peakIndex, nums[peakIndex]);
    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]) {

compare mid element with right neighbor to decide search direction

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

move left pointer to right half if right neighbor is bigger

right = mid; // move left because peak is on left side or mid

move right pointer to mid if mid is bigger or equal

return left; // left == right is peak index

return the index where left and right meet, the peak

Output

Peak element index: 2, value: 20

Complexity Analysis

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

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 faster by reducing checks to logarithmic time

Edge Cases

Array with single element

Returns index 0 as the peak since it has no neighbors

DSA C

while (left < right) {

Strictly increasing array

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

DSA C

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

Strictly decreasing array

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

DSA C

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 neighbors to reduce search space.

Common Mistakes

Mistake: Checking mid element against left neighbor instead of right neighbor
Fix: Always compare mid with mid+1 to decide which half to search next

Mistake: Not handling the case when left == right properly, causing infinite loop
Fix: Use while (left < right) and return left after loop ends

Summary

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

Use when you want to find a local maximum quickly without scanning the entire array.

The key insight is comparing mid element with its right 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. An element that is greater than its neighbors

B. The smallest element in the array

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: Apply this to binary search context

   Binary search finds such an element by comparing mid element with neighbors to decide the 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 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 syntax to calculate the middle index in binary search in C?

easy

A. int mid = (high - low) * 2;

B. int mid = (low + high) / 2;

C. int mid = (low - high) / 2;

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

Solution

1. Step 1: Understand integer overflow risk in mid calculation

   Using (low + high) / 2 can overflow if low and high are large integers.

2. Step 2: Use safer formula to avoid overflow

   Calculate mid as low + (high - low) / 2 to prevent overflow.

3. Final Answer:

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

4. Quick Check:

   Safe mid calculation = low + (high - low) / 2 [OK]

Hint: Use low + (high - low)/2 to avoid overflow [OK]

Common Mistakes:

• Using (low + high)/2 causing overflow
• Subtracting incorrectly in mid calculation
• Multiplying instead of dividing

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

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Identify peak candidates in the array

   Array: [1, 3, 20, 4, 1, 0]. Element 20 at index 2 is greater than neighbors 3 and 4.

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

   Binary search compares mid elements and moves towards the peak, landing on index 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Peak element index = 2 [OK]

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

Common Mistakes:

• Choosing first or last element incorrectly
• Confusing index with value
• Ignoring neighbors in peak definition

4. Consider this code snippet to find a peak element index:

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

What is the bug in this code?

medium

A. It should return high instead of low

B. The while condition should be low <= high

C. The else branch should set high = mid, not mid - 1

D. The mid calculation causes overflow

Solution

1. Step 1: Analyze the else branch update of high

   Setting high = mid - 1 skips the mid element which could be a peak.

2. Step 2: Correct update to include mid in search

   Change to high = mid to keep mid in the search space for peak.

3. Final Answer:

   The else branch should set high = mid, not mid - 1 -> Option C

4. Quick Check:

   Keep mid in search by high = mid [OK]

Hint: Use high = mid to avoid skipping potential peak [OK]

Common Mistakes:

• Reducing high too early and missing peak
• Changing while condition unnecessarily
• Ignoring mid element in binary search

5. Given an array [10, 20, 15, 2, 23, 90, 67], how many peak elements can binary search find and which index will it return if it always moves towards the right when equal?

hard

A. 2 peaks, returns index 5

B. 3 peaks, returns index 1

C. 1 peak, returns index 6

D. 2 peaks, returns index 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) and 90 (index 5) as both are greater than neighbors.

2. Step 2: Understand binary search behavior moving right on equal

   Binary search will move towards the right peak at index 5 because it moves right when equal or increasing.

3. Final Answer:

   2 peaks, returns index 5 -> Option A

4. Quick Check:

   Two peaks, rightmost peak index 5 [OK]

Hint: Multiple peaks possible; binary search returns one found by direction [OK]

Common Mistakes:

• Assuming only one peak always
• Ignoring binary search direction rules
• Confusing peak count with returned index