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.