Find Peak Element Using Binary Search in DSA Javascript - Execution Trace

Concept Flow - Find Peak Element Using Binary Search

Start with low=0, high=n-1

↓

Calculate mid = (low+high)//2

↓

Compare nums[mid

↓

mid

↓

Move high = mid

↓

Repeat until low == high

↓

Return low as peak index

We repeatedly check the middle element and compare it with its right neighbor. If middle is greater, we move left; else, we move right. This narrows down to a peak element.

Execution Sample

DSA Javascript

function findPeakElement(nums) {
  let low = 0, high = nums.length - 1;
  while (low < high) {
    let mid = Math.floor((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 and mid+1 elements.

Execution Table

Step	Operation	low	high	mid	Compare nums[mid] and nums[mid+1]	Pointer Changes	Current Search Range	Peak Candidate
1	Initialize	0	5	-	-	-	[1, 3, 20, 4, 1, 0]	-
2	Calculate mid	0	5	2	nums[2]=20 > nums[3]=4	high = mid = 2	[1, 3, 20]	Index 2
3	Calculate mid	0	2	1	nums[1]=3 < nums[2]=20	low = mid + 1 = 2	[20]	Index 2
4	low == high	2	2	-	-	-	[20]	Index 2 (peak found)

💡 low equals high at index 2, peak element found at nums[2] = 20

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4 (Final)
low	0	0	2	2
high	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 has a peak. If nums[mid] > nums[mid+1], peak lies on left including mid (see step 2). This avoids out-of-bound errors and ensures progress.

Why does the loop stop when low equals high?

When low equals high, the search range narrows to one element, which must be a peak (step 4). No further division is possible, so we return low.

What if the array has multiple peaks?

This method finds any one peak, not necessarily the highest. The binary search narrows to a local peak by comparing neighbors (see steps 2 and 3).

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 the execution_table row for step 3.

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

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Compare nums[mid] and nums[mid+1]' column in the execution_table.

If nums[mid] was less than nums[mid+1] at step 2, what would happen to 'low'?

A low would stay the same

B low would become mid

C low would become mid + 1

D low would become high

💡 Hint

Refer to the 'Pointer Changes' column in step 2 of the execution_table.

Concept Snapshot

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

Full Transcript

This concept uses binary search to find a peak element in an array. We start with low and high pointers at the ends. We calculate mid and compare nums[mid] with nums[mid+1]. If nums[mid] is greater, the peak is on the left side including mid, so we move high to mid. Otherwise, the peak is on the right side, so we move low to mid + 1. We repeat until low equals high, which is the peak index. This method efficiently narrows down the search space by half each time.