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

Challenge - 5 Problems

❓ Predict Output

intermediate

Find Peak Element Output

What is the output of the following C code that finds a peak element index in the array using binary search?

DSA C

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]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

// Input array: [1, 3, 20, 4, 1, 0]

A 1

B 2

C 3

D 4

💡 Hint

Think about how the binary search moves left or right based on the comparison between mid and mid+1.

The function uses binary search to find a peak element index. It compares nums[mid] and nums[mid+1]. If nums[mid] is greater, the peak is on the left side including mid, so right = mid. Otherwise, the peak is on the right side excluding mid, so left = mid + 1. For the input [1, 3, 20, 4, 1, 0], the peak is at index 2 with value 20.

❓ Predict Output

intermediate

Find Peak Element Output with Multiple Peaks

What is the output index of a peak element for the input array [10, 20, 15, 2, 23, 90, 67] using the binary search peak finding function?

DSA C

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]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

// Input array: [10, 20, 15, 2, 23, 90, 67]

A 5

B 6

C 4

D 1

💡 Hint

The function returns one peak index, not necessarily the first or last peak.

The function finds a peak element index using binary search. For the input, there are multiple peaks: 20 at index 1 and 90 at index 5. The binary search will find index 5 because it moves towards the right peak due to comparisons.

🧠 Conceptual

advanced

Why Binary Search Works for Peak Element?

Why does the binary search approach work to find a peak element in an unsorted array?

A Because the binary search always checks all elements sequentially.

B Because the array has only one peak element guaranteed.

C Because the array is sorted, so the peak is the maximum element.

D Because if nums[mid] > nums[mid+1], a peak must exist on the left side including mid.

💡 Hint

Think about how the comparison between nums[mid] and nums[mid+1] guides the search.

The binary search works because if nums[mid] > nums[mid+1], then a peak must exist on the left side including mid. Otherwise, the peak is on the right side. This logic ensures the search space reduces correctly to find a peak.

🔧 Debug

advanced

Identify the Bug in Peak Element Code

What error will occur when running this code to find a peak element?

DSA C

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]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

// Input array: [1, 2, 3, 1]

A Returns wrong peak index

B Infinite loop

C Array index out of bounds error

D No error, returns correct peak index

💡 Hint

Check the condition that accesses nums[mid + 1].

The loop condition allows mid to be equal to right, which can be numsSize - 1. Accessing nums[mid + 1] then causes an out of bounds error.

🚀 Application

expert

Find Peak Element in a Circular Array

Given a circular array where the end connects to the start, which modification to the binary search peak finding algorithm is correct to find a peak element?

A Compare nums[mid] with nums[(mid + 1) % numsSize] and nums[(mid - 1 + numsSize) % numsSize] to decide search direction.

B Use linear search because binary search does not work on circular arrays.

C Ignore circularity and apply normal binary search comparing nums[mid] and nums[mid+1].

D Sort the array first, then apply binary search to find the peak.

💡 Hint

Think about how to handle neighbors in a circular array.

In a circular array, neighbors wrap around. So to find a peak, compare nums[mid] with both neighbors using modulo to handle wrapping. This guides the binary search correctly.

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