Find Peak Element Using Binary Search in DSA Rust - Execution Trace

Concept Flow - Find Peak Element Using Binary Search

Start with array and low=0, high=n-1

↓

Calculate mid = (low+high)/2

↓

Compare nums[mid

↓

nums[mid

| No↓

Move high to mid

↓

Check if low == high

↓

Return low as peak index

We repeatedly check the middle element and compare it with its right neighbor to decide which half to search next until low meets high, which is the peak.

Execution Sample

DSA Rust

fn find_peak(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] {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    low
}

This code finds a peak element index in the array using binary search by comparing middle elements with their neighbors.

Execution Table

Step	Operation	low	high	mid	Compare nums[mid] and nums[mid+1]	Action	Current Search Range
1	Initialize	0	5	-	-	-	[1, 3, 20, 4, 1, 0]
2	Calculate mid	0	5	2	nums[2]=20 vs nums[3]=4	20 >= 4, move high to mid=2	[1, 3, 20]
3	Calculate mid	0	2	1	nums[1]=3 vs nums[2]=20	3 < 20, move low to mid+1=2	[20]
4	Check low vs high	2	2	-	-	low == high, stop	[20]

💡 low equals high at index 2, which is the peak element index.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4 (Final)
low	0	0	2	2
high	5	2	2	2
mid	-	2	1	-

Key Moments - 3 Insights

Why do we compare nums[mid] with nums[mid+1] and not nums[mid-1]?

Comparing nums[mid] with nums[mid+1] helps decide which side has a peak because if nums[mid] < nums[mid+1], the peak must be on the right side. This is shown in execution_table rows 2 and 3 where the decision to move low or high depends on this comparison.

Why does the loop stop when low equals high?

When low equals high, it means the search space has narrowed down to one element, which must be a peak. This is shown in execution_table row 4 where low and high both are 2, so the loop ends and returns the peak index.

What happens if the array has only one element?

If the array has one element, low and high start at 0, so the loop condition low < high is false immediately, and the function returns 0 as the peak index directly.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the value of low after the action?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Action' column at Step 3 where low is updated to mid+1 = 2.

At which step does the condition low < high become false?

A Step 2

B Step 3

C Step 4

D Never

💡 Hint

Look at Step 4 where low equals high, so the loop stops.

If nums[mid] was always greater than nums[mid+1], what would happen to the search range?

A low would keep increasing

B high would keep decreasing

C low and high would stay the same

D The loop would never end

💡 Hint

Refer to the 'Action' column where nums[mid] >= nums[mid+1] causes high to move to mid.

Concept Snapshot

Find Peak Element Using Binary Search:
- Initialize low=0, high=n-1
- While low < high:
  - mid = (low+high)//2
  - If nums[mid] < nums[mid+1], low = mid+1
  - Else high = mid
- Return low as peak index
This finds a peak in O(log n) time.

Full Transcript

This visualization shows how to find a peak element in an array using binary search. We start with low at 0 and high at the last index. We calculate mid and compare nums[mid] with nums[mid+1]. If nums[mid] is less, we move low to mid+1 to search the right half. Otherwise, we move high to mid to search the left half. We repeat until low equals high, which is the peak index. The execution table traces each step with variable values and decisions. Key moments clarify why we compare with nums[mid+1], why the loop stops when low equals high, and what happens with single-element arrays. The quiz tests understanding of variable changes and loop termination. This method efficiently finds a peak in logarithmic time.

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