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

Concept Flow - Find Peak Element Using Binary Search

Start with array boundaries: left=0, right=n-1

↓

Calculate mid = (left+right)/2

↓

Compare nums[mid

↓

mid

↓

Move right boundary to mid

↓

Move left boundary to mid+1

↓

Repeat until left == right

↓

Return left as peak index

We repeatedly check the middle element and compare it with its right neighbor to decide which half contains a peak, narrowing the search until we find a peak.

Execution Sample

DSA Go

func findPeakElement(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := (left + right) / 2
        if nums[mid] < nums[mid+1] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

This code finds a peak element index in the array using binary search by comparing middle elements with their neighbors.

Execution Table

Step	Operation	left	right	mid	Compare nums[mid] < nums[mid+1]	Action	Visual State (nums with pointers)
1	Initialize	0	5	-	-	-	nums=[1, 3, 20, 4, 1, 0], left=0, right=5
2	Calculate mid	0	5	2	20 < 4? False	right = mid	nums=[1, 3, 20, 4, 1, 0], left=0, right=2
3	Calculate mid	0	2	1	3 < 20? True	left = mid + 1	nums=[1, 3, 20, 4, 1, 0], left=2, right=2
4	Check left < right	2	2	-	-	left == right, stop	nums=[1, 3, 20, 4, 1, 0], peak at index 2

💡 left equals right at index 2, which is a peak element

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4 (final)
left	0	0	2	2
right	5	2	2	2
mid	-	2	1	1 (last calculated)

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 on the right or left side. If nums[mid] < nums[mid+1], the peak must be right of mid, so we move left boundary. This is shown in execution_table row 2 and 3.

Why does the loop stop when left equals right?

When left equals right, it means the search space is narrowed down to one element, which must be a peak. This is the exit condition shown in execution_table row 4.

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 as shown by the pointer movements in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what is the value of mid and what comparison is made?

A mid=3, compare nums[3]=4 < nums[4]=1

B mid=1, compare nums[1]=3 < nums[2]=20

C mid=2, compare nums[2]=20 < nums[3]=4

D mid=0, compare nums[0]=1 < nums[1]=3

💡 Hint

Check the 'mid' and 'Compare nums[mid] < nums[mid+1]' columns in execution_table row 2

At which step does the left pointer move to mid+1?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the 'Action' column in execution_table row 3

If nums[mid] was always greater than nums[mid+1], what would happen to the pointers?

A right would keep moving to mid

B left would keep increasing

C left and right would not change

D loop would never end

💡 Hint

Refer to the 'Action' column where nums[mid] < nums[mid+1] is false, right is set to mid

Concept Snapshot

Find Peak Element Using Binary Search:
- Use two pointers: left=0, right=n-1
- While left < right:
  - mid = (left+right)//2
  - If nums[mid] < nums[mid+1], move left to mid+1
  - Else move right to mid
- When left == right, return left 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 two pointers at the ends of the array. We calculate the middle index and compare the middle element with its right neighbor. If the middle element is less than its right neighbor, the peak lies to the right, so we move the left pointer to mid+1. Otherwise, the peak lies to the left or at mid, so we move the right pointer to mid. We repeat this until left equals right, which is the peak index. This method efficiently narrows down the search space by half each time, ensuring a peak is found quickly.