Find Peak Element Using Binary Search in DSA Rust

Mental Model

A peak element is one that is bigger than its neighbors. We can find it fast by cutting the search area in half each time.

Analogy: Imagine climbing a mountain range in fog. If you step uphill, keep going that way because the peak is ahead. If you step downhill, turn back because the peak is behind. This way, you find a peak without seeing the whole range.

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: Set low=0, high=6, mid=(0+6)//2=3, compare arr[3]=4 and arr[4]=1

Array: 1 -> 3 -> 20 -> [4] -> 1 -> 0 -> 5
Pointers: low=0, mid=3, high=6

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

Step 2: Since arr[3]=4 > arr[4]=1, move high to mid=3

Array: 1 -> 3 -> 20 -> [4] -> 1 -> 0 -> 5
Pointers: low=0, mid=3, high=3

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

Step 3: Calculate mid=(0+3)//2=1, compare arr[1]=3 and arr[2]=20

Array: 1 -> [3] -> 20 -> 4 -> 1 -> 0 -> 5
Pointers: low=0, mid=1, high=3

Why: Check if peak is on right side because arr[mid] < arr[mid+1]

Step 4: Since arr[1]=3 < arr[2]=20, move low to mid+1=2

Array: 1 -> 3 -> [20] -> 4 -> 1 -> 0 -> 5
Pointers: low=2, mid=1, high=3

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

Step 5: Calculate mid=(2+3)//2=2, compare arr[2]=20 and arr[3]=4

Array: 1 -> 3 -> [20] -> 4 -> 1 -> 0 -> 5
Pointers: low=2, mid=2, high=3

Why: Check if mid is peak by comparing with next element

Step 6: Since arr[2]=20 > arr[3]=4, move high to mid=2

Array: 1 -> 3 -> [20] -> 4 -> 1 -> 0 -> 5
Pointers: low=2, mid=2, high=2

Why: Peak is at mid or left side because arr[mid] > arr[mid+1]

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

Array: 1 -> 3 -> [20] -> 4 -> 1 -> 0 -> 5
Pointers: low=2, high=2

Why: When low meets high, peak found

Result:

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

Annotated Code

DSA Rust

fn find_peak_element(nums: &[i32]) -> usize {
    let mut low = 0;
    let mut high = nums.len() - 1;
    while low < high {
        let mid = (low + high) / 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
        }
    }
    low // low == high is peak index
}

fn main() {
    let arr = [1, 3, 20, 4, 1, 0, 5];
    let peak_index = find_peak_element(&arr);
    println!("Peak element index: {}, value: {}", peak_index, arr[peak_index]);
}

while low < high {

loop until search space narrows to one element

let mid = (low + high) / 2;

find middle index to check peak condition

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

compare mid 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

low // low == high is peak index

return the peak index when search space is one

Output

Peak element index: 2, value: 20

Complexity Analysis

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

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 because it's the only element

DSA Rust

let mut high = nums.len() - 1;

Strictly increasing array

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

DSA Rust

low = mid + 1;

Strictly decreasing array

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

DSA Rust

high = mid;

When to Use This Pattern

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

Common Mistakes

Mistake: Comparing mid element with previous instead of next element
Fix: Always compare nums[mid] with nums[mid + 1] to decide direction

Mistake: Not handling single element array causing index out of bounds
Fix: Initialize high as nums.len() - 1 and ensure array length > 0 before calling

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 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. An element equal to its neighbors

B. The smallest element in the array

C. The first element of the array

D. An element greater than 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 an edge).

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 greater than its neighbors -> Option D

4. Quick Check:

   Peak element = element greater than neighbors [OK]

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

Common Mistakes:

• Confusing peak with smallest element
• Thinking peak must be at array start
• Assuming peak equals neighbors

2. Which Rust code snippet correctly initializes the binary search boundaries for finding a peak element in a vector nums?

easy

A. let (mut left, mut right) = (0, nums.len() - 1);

B. let (left, right) = (1, nums.len());

C. let (mut left, mut right) = (1, nums.len() - 1);

D. let (left, right) = (0, nums.len());

Solution

1. Step 1: Identify correct boundary initialization

   Binary search on array indices starts at 0 and ends at length - 1 because indexing is zero-based.

2. Step 2: Check mutability and correct tuple assignment

   We need mutable variables for left and right to update during search, so use mut and assign (0, nums.len() - 1).

3. Final Answer:

   let (mut left, mut right) = (0, nums.len() - 1); -> Option A

4. Quick Check:

   Start=0, End=length-1, mutable [OK]

Hint: Start at 0, end at length-1 with mut for binary search [OK]

Common Mistakes:

• Using length instead of length - 1 as right boundary
• Not declaring variables as mutable
• Starting from 1 instead of 0

3. What will be the output index of the peak element for the input array nums = vec![1, 3, 2, 1] using binary search peak finding?

medium

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Analyze the array and identify peak candidates

   Array is [1, 3, 2, 1]. Element at index 1 is 3, which is greater than neighbors 1 and 2.

2. Step 2: Confirm binary search would find index 1

   Binary search compares mid with neighbors and moves left or right. Mid initially at index 1 or 2 will find 3 as peak.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Peak element 3 at index 1 [OK]

Hint: Peak is local max, here 3 at index 1 [OK]

Common Mistakes:

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

4. Identify the bug in this Rust code snippet for finding a peak element using binary search:

let mut left = 0;
let mut right = nums.len();
while left < right {
    let mid = (left + right) / 2;
    if nums[mid] < nums[mid + 1] {
        left = mid + 1;
    } else {
        right = mid;
    }
}
return left;

medium

A. Right boundary should be nums.len() - 1

B. Mid calculation causes overflow

C. Comparison should be nums[mid] > nums[mid + 1]

D. Loop condition should be left <= right

Solution

1. Step 1: Check boundary initialization

   Right boundary is set to nums.len(), which is out of valid index range (max index is len - 1).

2. Step 2: Understand impact on mid + 1 access

   Accessing nums[mid + 1] can cause out-of-bounds panic if mid is at last index due to wrong right boundary.

3. Final Answer:

   Right boundary should be nums.len() - 1 -> Option A

4. Quick Check:

   Right = len - 1 to avoid out-of-bounds [OK]

Hint: Right boundary must be last valid index (len-1) [OK]

Common Mistakes:

• Setting right to length instead of length - 1
• Ignoring out-of-bounds access on mid + 1
• Changing loop condition incorrectly

5. Given a vector nums = vec![1, 2, 3, 1, 5, 6, 4], which index will the binary search peak finding algorithm return and why?

hard

A. 2, because 3 is a peak before the drop

B. 3, because 1 is the middle element

C. 5, because 6 is a peak after the drop

D. 6, because 4 is the last element

Solution

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

   Array: [1, 2, 3, 1, 5, 6, 4]. Peaks are elements greater than neighbors: 3 at index 2 and 6 at index 5.

2. Step 2: Trace binary search behavior

   left=0, right=6; mid=3 (1 < 5), left=4; mid=5 (6 > 4), right=5; mid=4 (5 < 6), left=5. Returns index 5.

3. Final Answer:

   5, because 6 is a peak after the drop -> Option C

4. Quick Check:

   Binary search finds peak at index 5 [OK]

Hint: Binary search returns any peak; trace steps to confirm which [OK]

Common Mistakes:

• Assuming it always finds the first peak
• Choosing middle element without checking neighbors
• Ignoring multiple peaks in array