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

We repeatedly check the middle element and compare it with its right neighbor to decide which half to search next until low meets high, which is the peak.

Execution Sample

DSA Typescript

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

Execution Table

Step	Operation	low	high	mid	nums[mid]	nums[mid+1]	Condition (nums[mid] < nums[mid+1])	Action	Visual State (nums array with low, mid, high)
1	Initialize	0	5	-	-	-	-	Start loop	nums=[1,3,20,4,1,0], low=0, high=5
2	Calculate mid	0	5	2	20	4	False	high = mid	low=0, mid=2, high=5
3	Calculate mid	0	2	1	3	20	True	low = mid + 1	low=0, mid=1, high=2
4	Calculate mid	2	2	2	20	4	False	high = mid	low=2, mid=2, high=2
5	Check low == high	2	2	-	-	-	-	Return low=2	Peak at index 2 with value 20

💡 Loop ends when low equals high, indicating peak element found at index 2.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
low	0	0	1	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]?

Comparing nums[mid] with nums[mid+1] helps decide if the peak is to the right or left. If nums[mid] < nums[mid+1], peak must be right, so we move low up. This is shown in execution_table rows 2 and 3 where the condition guides the search direction.

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 is the peak. This is the termination condition shown in execution_table row 5.

What if the array has multiple peaks?

This method finds any one peak, not necessarily the highest. The binary search ensures it finds a local peak by moving towards the side that has a higher neighbor, as seen in the actions in execution_table rows 2-4.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the value of 'low' after the action?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Action' column at Step 3 where low is updated to mid + 1.

At which step does the condition nums[mid] < nums[mid+1] become false for the first time?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the 'Condition' column in execution_table; false first appears at Step 2.

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

A It would increase until it equals high

B It would decrease

C It would stay the same

D It would become negative

💡 Hint

Refer to the 'Action' column where low is set to mid + 1 when condition is true.

Concept Snapshot

Find Peak Element Using Binary Search:
- Initialize low=0, high=n-1
- While low < high:
  - mid = (low+high)//2
  - If nums[mid] < nums[mid+1], low = mid+1
  - Else high = mid
- Return low as peak index
This finds a local peak efficiently in O(log n) time.

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 mid with mid+1 and why the loop stops when low equals high. The quiz tests understanding of variable changes and conditions during the search.

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 which half to search next.

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:

• Thinking peak is smallest element
• Confusing peak with first or last element always
• Assuming peak equals neighbors

2. Which of the following is the correct TypeScript syntax to start a binary search loop for finding a peak element in array nums?

easy

A. while(left < right) { ... }

B. if(nums[mid] > nums[mid+1]) { ... }

C. for(let i = 0; i < nums.length; i++)

D. switch(nums[mid]) { ... }

Solution

1. Step 1: Identify the loop type for binary search

   Binary search uses a while loop with condition left < right to narrow down the search range.

2. Step 2: Check options for correct binary search syntax

   while(left < right) { ... } shows the correct while loop structure for binary search.

3. Final Answer:

   while(left < right) { ... } -> Option A

4. Quick Check:

   Binary search uses while loop [OK]

Hint: Binary search uses while(left < right) loop [OK]

Common Mistakes:

• Using for loop instead of while
• Using if instead of loop for search
• Using switch incorrectly for binary search

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

medium

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Identify peak elements in the array

   Check neighbors: 20 at index 2 is greater than 3 and 4, so it's a peak.

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

   Binary search compares mid with neighbors and narrows to index 2.

3. Final Answer:

   2 -> Option C

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 incorrectly
• Confusing peak with global max always
• Ignoring neighbors in peak definition

4. Given this TypeScript code snippet to find a peak element, what is the bug?

let left = 0;
let right = nums.length - 1;
while (left < right) {
  let mid = Math.floor((left + right) / 2);
  if (nums[mid] < nums[mid + 1]) {
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}
return left;

medium

A. Return should be right instead of left

B. The loop condition should be while(left <= right)

C. The mid calculation is incorrect

D. The else branch should set right = mid, not mid - 1

Solution

1. Step 1: Analyze the else branch update of right pointer

   Setting right = mid - 1 skips the mid element, possibly missing peak.

2. Step 2: Correct approach is right = mid to keep mid in range

   To ensure peak is not skipped, right should be set to mid, not mid - 1.

3. Final Answer:

   The else branch should set right = mid, not mid - 1 -> Option D

4. Quick Check:

   Keep mid in range by right = mid [OK]

Hint: Use right = mid to avoid skipping mid element [OK]

Common Mistakes:

• Setting right = mid - 1 causing missed peaks
• Changing loop condition unnecessarily
• Miscomputing mid index

5. You have an array nums = [10, 20, 15, 2, 23, 90, 67]. Using binary search to find a peak element, which index could be returned as a valid peak?

hard

A. 2

B. 5

C. 6

D. 3

Solution

1. Step 1: Identify all peak elements in the array

   Peaks are elements greater than neighbors: 20 at index 1 and 90 at index 5.

2. Step 2: Binary search can return any peak; index 5 (value 90) is a valid peak

   90 is greater than 23 and 67, so index 5 is a valid peak.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   90 at index 5 is peak [OK]

Hint: Binary search may return any peak, here index 5 is valid [OK]

Common Mistakes:

• Assuming only one peak exists
• Choosing non-peak elements
• Ignoring neighbors when checking peak