Find Peak Element Using Binary Search in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find Peak Element Output

What is the output index of the peak element for the given array using binary search?

DSA Rust

fn find_peak_element(nums: &[i32]) -> usize {
    let mut left = 0;
    let mut right = nums.len() - 1;
    while left < right {
        let mid = (left + right) / 2;
        if nums[mid] > nums[mid + 1] {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    left
}

fn main() {
    let nums = [1, 3, 20, 4, 1, 0];
    let peak_index = find_peak_element(&nums);
    println!("{}", peak_index);
}

A 5

B 2

C 3

D 1

💡 Hint

Think about how the binary search compares middle elements with their neighbors to find a peak.

The function uses binary search to find a peak element index. It compares the middle element with the next one. If the middle is greater, the peak is on the left side including mid; otherwise, it's on the right side. For the array [1, 3, 20, 4, 1, 0], the peak is at index 2 (value 20).

🧠 Conceptual

intermediate

Understanding Peak Element Conditions

Which condition correctly identifies a peak element at index i in an array nums?

A nums[i] < nums[i - 1] and nums[i] < nums[i + 1]

B nums[i] >= nums[i - 1] or nums[i] >= nums[i + 1]

C nums[i] > nums[i - 1] and nums[i] > nums[i + 1]

D nums[i] == nums[i - 1] or nums[i] == nums[i + 1]

💡 Hint

A peak element is greater than both neighbors.

A peak element is strictly greater than its neighbors. Option C correctly states this condition. Other options either use or conditions or check for equality or smaller values, which do not define a peak.

🔧 Debug

advanced

Identify the Bug in Peak Element Binary Search

What error will this Rust code produce when run, and why?

DSA Rust

fn find_peak_element(nums: &[i32]) -> usize {
    let mut left = 0;
    let mut right = nums.len();
    while left < right {
        let mid = (left + right) / 2;
        if nums[mid] > nums[mid + 1] {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    left
}

fn main() {
    let nums = [1, 2, 3, 1];
    let peak_index = find_peak_element(&nums);
    println!("{}", peak_index);
}

A Returns incorrect peak index 0

B Compilation error due to missing semicolon

C Infinite loop because left and right never converge

D Index out of bounds panic at nums[mid + 1]

💡 Hint

Check the range of right and how mid + 1 is accessed.

The code sets right to nums.len(), which is out of bounds for indexing. When mid equals nums.len() - 1, mid + 1 equals nums.len(), causing an index out of bounds panic.

📝 Syntax

advanced

Which Rust Code Correctly Implements Peak Element Binary Search?

Select the option that compiles and correctly finds a peak element index.

A

fn find_peak(nums: &[i32]) -> usize {
    let mut left = 0;
    let mut right = nums.len() - 1;
    while left < right {
        let mid = (left + right) / 2;
        if nums[mid] < nums[mid + 1] {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    left
}

B

fn find_peak(nums: &[i32]) -> usize {
    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 - 1;
        }
    }
    left
}

C

fn find_peak(nums: &[i32]) -> usize {
    let mut left = 0;
    let mut right = nums.len() - 1;
    while left <= right {
        let mid = (left + right) / 2;
        if nums[mid] < nums[mid + 1] {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    left
}

D

fn find_peak(nums: &[i32]) -> usize {
    let mut left = 0;
    let mut right = nums.len() - 1;
    while left < right {
        let mid = (left + right) / 2;
        if nums[mid] > nums[mid + 1] {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    left
}

💡 Hint

Check the loop condition and how left and right are updated to avoid out of bounds and infinite loops.

Option A correctly uses while left < right and updates left and right pointers safely. It avoids index out of bounds and infinite loops. Other options either use wrong loop conditions or unsafe indexing.

🚀 Application

expert

Find Peak Element in a Large Array Efficiently

Given a large array where multiple peak elements exist, which approach ensures finding any peak element in O(log n) time?

A Use binary search comparing mid element with neighbors to decide search direction

B Use linear scan to check each element until a peak is found

C Sort the array and pick the middle element as peak

D Use recursion to check all elements simultaneously

💡 Hint

Think about how binary search reduces search space by half each step.

Binary search compares the middle element with its neighbor to decide which half contains a peak, reducing the search space logarithmically. Linear scan is O(n), sorting is O(n log n) and does not guarantee peak, recursion checking all elements is inefficient.

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