Find Peak Element Using Binary Search in DSA C - 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

The binary search narrows down the search space by comparing middle element with its right neighbor, moving towards the peak until low meets high.

Execution Sample

DSA C

int findPeakElement(int* nums, int numsSize) {
  int low = 0, high = numsSize - 1;
  while (low < high) {
    int mid = (low + high) / 2;
    if (nums[mid] < nums[mid + 1])
      low = mid + 1;
    else
      high = mid;
  }
  return low;
}

This code finds a peak element index in the array using binary search by comparing mid element with its next element.

Execution Table

Step	Operation	low	high	mid	Compare nums[mid] and nums[mid+1]	Action	Visual State (Array with low, mid, high)
1	Initialize low and high	0	5	-	-	Start searching	[1, 3, 20, 4, 1, 0] low=0 high=5
2	Calculate mid	0	5	2	nums[2]=20 vs nums[3]=4	20 > 4, move high to mid=2	[1, 3, 20, 4, 1, 0] low=0 mid=2 high=5
3	Calculate mid	0	2	1	nums[1]=3 vs nums[2]=20	3 < 20, move low to mid+1=2	[1, 3, 20, 4, 1, 0] low=2 mid=1 high=2
4	Check low < high	2	2	-	-	low == high, stop	[1, 3, 20, 4, 1, 0] low=2 high=2
5	Return low as peak index	2	2	-	-	Peak at index 2 with value 20	[1, 3, 20, 4, 1, 0] peak=2

💡 low equals high at index 2, peak found at index 2

Variable Tracker

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

Key Moments - 3 Insights

Why do we compare nums[mid] with nums[mid+1] instead of nums[mid-1]?

Comparing nums[mid] with nums[mid+1] helps decide which side the peak lies on. If nums[mid] < nums[mid+1], peak is on the right side, so we move low up. This is shown in execution_table rows 2 and 3.

Why does the loop stop when low equals high?

When low equals high, the search space has narrowed to one element, which must be a peak. This is the termination condition shown in execution_table row 4.

What if the array has multiple peaks?

The binary search will find any one peak because it moves towards a higher neighbor. The exact peak found depends on comparisons, as seen in the steps narrowing to index 2.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of mid at step 3?

A 1

B 2

C 0

D 3

💡 Hint

Check the 'mid' column in execution_table row 3

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

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Action' and 'Operation' columns in execution_table row 4

If nums[mid] was always greater than nums[mid+1], how would the search space change?

A low would move up each time

B low and high would not change

C high would move down each time

D The loop would never end

💡 Hint

Refer to the 'Action' column in execution_table rows where nums[mid] > nums[mid+1]

Concept Snapshot

Find Peak Element Using Binary Search:
- Use low=0, high=n-1
- While low < high:
  - mid = (low+high)/2
  - If nums[mid] < nums[mid+1], low = mid+1
  - Else high = mid
- When low == high, return low as peak index
- Works because peak is where nums[mid] > neighbors

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 up to mid+1, else we move high down to mid. 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 how multiple peaks are handled. The quiz tests understanding of mid values, loop termination, and pointer movements. This method efficiently finds a peak in O(log n) time.

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