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 hiking on a mountain trail where you want to find a peak. You stand in the middle and look around. If the slope goes up to the right, you walk right; if it goes up to the left, you walk left. Eventually, you reach a peak where the ground is higher than both sides.

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 element is greater than neighbors

Step 1: Check middle element at index 3 (value 4)

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

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

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

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

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

Step 3: Check middle element at index 1 (value 3)

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

Why: Narrow search to left half, check new middle

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

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

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

Step 5: Check middle element at index 2 (value 20)

Array: [20↑] -> 4

Why: Check middle of new range

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

Peak element at index 2 with value 20

Why: Element greater than neighbors is a peak

Result:

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

Annotated Code

DSA C#

using System;

class PeakElementFinder
{
    public static int FindPeakElement(int[] nums)
    {
        int left = 0;
        int right = nums.Length - 1;

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

            // Compare middle element with its right neighbor
            if (nums[mid] < nums[mid + 1])
            {
                // Peak must be in right half
                left = mid + 1;
            }
            else
            {
                // Peak is in left half or at mid
                right = mid;
            }
        }

        // left and right converge to peak index
        return left;
    }

    static void Main()
    {
        int[] nums = {1, 3, 20, 4, 1, 0, 5};
        int peakIndex = FindPeakElement(nums);
        Console.WriteLine($"{string.Join(" -> ", nums)} -> null");
        Console.WriteLine($"Peak element index: {peakIndex}, value: {nums[peakIndex]}");
    }
}

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 middle with right neighbor to decide search direction

left = mid + 1;

move left pointer to right half if slope goes up

right = mid;

move right pointer to mid if slope goes down or peak found

return left;

return the index where left and right converge, the peak

Output

1 -> 3 -> 20 -> 4 -> 1 -> 0 -> 5 -> null

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

Array with single element

Returns index 0 as 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#

else { right = mid; }

When to Use This Pattern

When you need to find a local maximum quickly in an unsorted array, use binary search on the slope direction to find a peak efficiently.

Common Mistakes

Mistake: Checking neighbors without handling array boundaries causing index errors
Fix: Always compare mid with mid+1 inside loop where mid+1 is guaranteed to be valid

Summary

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

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

The key insight is to use the slope between mid and mid+1 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 first element of the array

B. An element that is smaller than its neighbors

C. An element that is greater than its neighbors

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 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 C

4. Quick Check:

   Peak element = greater than neighbors [OK]

Hint: Peak element > neighbors, use binary search to find it fast [OK]

Common Mistakes:

• Confusing peak with minimum element
• Thinking peak must be at array ends
• Assuming peak equals maximum element in array

2. Which of the following is the correct C# syntax to calculate the middle index in binary search to avoid overflow?

easy

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

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

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

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

Solution

1. Step 1: Understand overflow risk in mid calculation

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

2. Step 2: Use safe calculation 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
• Mixing up low and high in formula

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. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Identify peak candidates in the array

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

2. Step 2: Binary search finds peak at index 2

   Binary search compares mid elements and narrows down to index 2 as peak.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Peak element index = 2 [OK]

Hint: Peak is local max; check neighbors to confirm [OK]

Common Mistakes:

• Choosing first or last element incorrectly
• Confusing peak with global max
• Not checking both neighbors

4. Identify the error in this C# binary search code snippet for finding a peak element:

int mid = low + (high - low) / 2;
if (arr[mid] < arr[mid + 1])
    low = mid + 1;
else
    high = mid - 1;

medium

A. It may cause index out of range when mid is at the last element

B. The mid calculation can overflow

C. The condition should be arr[mid] > arr[mid + 1]

D. The else block should set low = mid + 1

Solution

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

   If mid is the last index, arr[mid + 1] causes index out of range error.

2. Step 2: Need to ensure mid + 1 is within array bounds

   Code must check or limit mid to avoid accessing beyond array length.

3. Final Answer:

   It may cause index out of range when mid is at the last element -> Option A

4. Quick Check:

   Check array bounds before accessing mid+1 [OK]

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

Common Mistakes:

• Ignoring array boundary causing runtime errors
• Incorrect mid calculation causing overflow
• Wrong comparison direction in if condition

5. Given a mountain array [0, 2, 4, 7, 5, 3, 1], which modification to the binary search algorithm helps find the peak element efficiently?

hard

A. Compare mid with mid+1 and move low or high accordingly

B. Always move low to mid+1 regardless of comparison

C. Use linear search instead of binary search

D. Compare mid with mid-1 and move high to mid-1 always

Solution

1. Step 1: Understand mountain array property

   Mountain array increases then decreases, so peak is where arr[mid] > arr[mid+1].

2. Step 2: Use binary search comparing mid and mid+1

   If arr[mid] < arr[mid+1], move low to mid+1; else move high to mid to find peak.

3. Final Answer:

   Compare mid with mid+1 and move low or high accordingly -> Option A

4. Quick Check:

   Compare mid and mid+1 to find peak [OK]

Hint: Compare mid and mid+1 to decide search direction [OK]

Common Mistakes:

• Moving pointers incorrectly ignoring array shape
• Using linear search losing binary search efficiency
• Comparing mid with mid-1 incorrectly