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

↓

Check if nums[mid

Yes No↓

high = mid

↓

Repeat until low == high

↓

Return low (peak index)

We repeatedly check the middle element to see if it is a peak. If not, we move to the half that must contain a peak, narrowing the search until we find one.

Execution Sample

DSA C++

int findPeakElement(vector<int>& nums) {
  int low = 0, high = nums.size() - 1;
  while (low < high) {
    int mid = (low + high) / 2;
    if (nums[mid] > nums[mid + 1]) high = mid;
    else low = mid + 1;
  }
  return low;
}

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

Execution Table

Step	Operation	low	high	mid	Check Condition	Action	Visual State (nums with mid)
1	Initialize	0	5	-	-	Start search	[1, 3, 20, 4, 1, 0] mid= -
2	Calculate mid	0	5	2	nums[2]=20 > nums[3]=4 ?	Yes, high = mid=2	[1, 3, 20, 4, 1, 0] mid=20
3	Calculate mid	0	2	1	nums[1]=3 > nums[2]=20 ?	No, low = mid+1=2	[1, 3, 20, 4, 1, 0] mid=3
4	Calculate mid	2	2	2	low == high, exit loop	Return low=2	[1, 3, 20, 4, 1, 0] mid=20
5	End	2	2	2	-	Peak found at index 2	[1, 3, 20, 4, 1, 0] peak=20

💡 Loop ends when low equals high, 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	2
high	5	2	2	2	2
mid	-	2	1	2	2

Key Moments - 3 Insights

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

Because the algorithm moves towards the side that must contain a peak. Checking nums[mid] > nums[mid + 1] tells us if the peak is on the left side including mid, else on the right side. This is shown in execution_table rows 2 and 3.

Why does the loop stop when low equals high?

When low equals high, it means the search space is narrowed down to one element, which must be a peak. This is shown in execution_table row 4 where low == high triggers loop exit.

What if the array has multiple peaks? Which one is returned?

The binary search returns any one peak it finds by moving towards a peak side. It does not guarantee the first or last peak, just a valid peak. This is implied by the narrowing steps in execution_table.

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 for Step 3.

At which step does the condition nums[mid] > nums[mid + 1] become false?

A Step 2

B Step 4

C Step 3

D Step 1

💡 Hint

Look at the 'Check Condition' column in execution_table for Steps 2 and 3.

If the array was strictly increasing, how would the 'low' pointer change?

A It would stay at 0

B It would move towards the right until it reaches the last index

C It would move towards the left

D It would jump randomly

💡 Hint

Refer to the 'Action' column where low is updated to mid+1 when 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], high = mid
  - Else low = mid+1
- Return low as peak index
Key: Compare mid with right neighbor to decide search side.

Full Transcript

This concept shows how to find a peak element in an array using binary search. We start with low and high pointers at the ends of the array. We calculate mid and check if it is a peak by comparing it with its right neighbor. If mid is greater, we move high to mid, else low moves to mid+1. 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 the right neighbor and when the loop ends. The quiz tests understanding of mid values, condition checks, and pointer movements. The snapshot summarizes the approach and key rule.

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. An element that is smaller than its neighbors

C. The first element of the array

D. The last element of the array

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 only 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 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 smaller [OK]

Common Mistakes:

• Confusing peak with smallest element
• Thinking peak is always first or last element
• Ignoring boundary conditions

2. Which of the following is the correct syntax to start binary search for peak element in C++?

easy

A. int left = 1, right = n;

B. int left = 0, right = n;

C. int left = 0, right = n - 1;

D. int left = 1, right = n - 1;

Solution

1. Step 1: Identify valid index range for array of size n

   Array indices go from 0 to n-1, so left should start at 0 and right at n-1.

2. Step 2: Check each option for correct initialization

   int left = 0, right = n - 1; correctly initializes left=0 and right=n-1, suitable for binary search.

3. Final Answer:

   int left = 0, right = n - 1; -> Option C

4. Quick Check:

   Index range = 0 to n-1 [OK]

Hint: Array indices start at 0, end at n-1 [OK]

Common Mistakes:

• Starting left at 1 instead of 0
• Setting right to n instead of n-1
• Confusing inclusive and exclusive ranges

3. What will be the output index of the peak element for the array [1, 3, 20, 4, 1, 0] using binary search peak finding?

medium

A. 0

B. 2

C. 3

D. 1

Solution

1. Step 1: Identify peak elements in the array

   Array: [1, 3, 20, 4, 1, 0]. 20 at index 2 is greater than neighbors 3 and 4, so it's a peak.

2. Step 2: Binary search will find index 2 as peak

   Binary search compares mid elements and moves left or right until it finds 20 at index 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Peak at index 2 = 20 [OK]

Hint: Peak is local max, here 20 at index 2 [OK]

Common Mistakes:

• Choosing first or last element as peak incorrectly
• Confusing index with value
• Not checking both neighbors

4. Given the following code snippet, what is the bug that prevents finding the peak element correctly?

int findPeak(int arr[], int n) {
  int left = 0, right = n - 1;
  while (left < right) {
    int mid = (left + right) / 2;
    if (arr[mid] < arr[mid + 1])
      left = mid + 1;
    else
      right = mid - 1;
  }
  return left;
}

medium

A. Decreasing right by 1 skips potential peak

B. Mid calculation causes overflow

C. Loop condition should be left <= right

D. Returning left instead of right

Solution

1. Step 1: Analyze the binary search update steps

   If arr[mid] >= arr[mid+1], the code sets right = mid - 1, which skips mid as a candidate peak.

2. Step 2: Correct approach is to set right = mid to include mid in search

   Setting right = mid keeps mid in range; subtracting 1 may miss the peak.

3. Final Answer:

   Decreasing right by 1 skips potential peak -> Option A

4. Quick Check:

   Right update must keep mid included [OK]

Hint: Do not exclude mid when moving right pointer [OK]

Common Mistakes:

• Setting right = mid - 1 instead of right = mid
• Ignoring mid element as possible peak
• Incorrect loop condition

5. You have an array [10, 20, 15, 2, 23, 90, 67]. Using binary search for peak element, which index will be returned and why?

hard

A. 0, because 10 is the first element

B. 1, because 20 is a peak element

C. 6, because 67 is the last element

D. 5, because 90 is a peak element

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). 90 is greater than neighbors 23 and 67.

2. Step 2: Binary search tends to find a peak, often the higher one

   Binary search will find 90 at index 5 because it is a higher peak than 20 at index 1.

3. Final Answer:

   5, because 90 is a peak element -> Option D

4. Quick Check:

   Highest peak found = index 5 [OK]

Hint: Binary search finds any peak; higher peaks likely found first [OK]

Common Mistakes:

• Assuming first peak is always returned
• Ignoring multiple peaks in array
• Confusing last element as peak without checking neighbors