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

↓

Move low=mid+1

↓

Else mid is peak

↓

Return mid

We repeatedly check the middle element and compare it with neighbors to decide which half to search next, narrowing down to a peak.

Execution Sample

DSA Python

def find_peak(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        mid = (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 with its right neighbor.

Execution Table

Step	low	high	mid	Compare nums[mid] and nums[mid+1]	Action	Current Search Range	Visual State
1	0	5	2	nums[2]=3 < nums[3]=4 is True	low = mid + 1 = 3	[3..5]	[1, 2, 3, 4, 3, 1]
2	3	5	4	nums[4]=3 < nums[5]=1 is False	high = mid = 4	[3..4]	[1, 2, 3, 4, 3, 1]
3	3	4	3	nums[3]=4 < nums[4]=3 is False	high = mid = 3	[3..3]	[1, 2, 3, 4, 3, 1]
4	3	3	-	Loop ends as low == high	Return low = 3	[3..3]	[1, 2, 3, 4, 3, 1]

💡 Loop ends when low equals high, pointing to a peak element index.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
low	0	3	3	3	3
high	5	5	4	3	3
mid	-	2	4	3	-

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], the peak must be right, so we move low up. This is shown in execution_table step 1 where low moves to mid+1.

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. This is shown in execution_table step 4 where low == high == 3, so we return low.

Can the peak be at the edges of the array?

Yes, the peak can be at the start or end if those elements are greater than their neighbors. The binary search approach still works because it narrows down to a peak anywhere in the array.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'low' after step 1?

A 2

B 3

C 0

D 5

💡 Hint

Check the 'low' column in execution_table row for step 1.

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

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

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

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

A It would be the last index

B It would be 0

C It would be the middle index

D It would be -1

💡 Hint

In a strictly increasing array, the peak is at the end, so low moves right each time.

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], low = mid+1
  - Else high = mid
- Return low as peak index
- Works because peak must be on side with higher neighbor

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 compare nums[mid] with nums[mid+1]. If nums[mid] is less, we move low to mid+1, else we move high to mid. We repeat until low equals high, which points to a peak. The execution table traces each step with variable values and decisions. Key moments clarify why we compare with the right neighbor and why the loop ends when low equals high. The visual quiz tests understanding of variable changes and conditions. The snapshot summarizes the approach in simple steps.

Practice

1. What is a peak element in an array when using binary search to find it?

easy

A. The first element of the array

B. An element that is greater than its neighbors

C. The smallest element in 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: Relate to binary search goal

   Binary search finds such an element by comparing middle elements with neighbors to decide search direction.

3. Final Answer:

   An element that is greater than its neighbors -> Option B

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 Python syntax to start a binary search loop for finding a peak element in array nums?

easy

A. while left <= right:

B. for i in nums:

C. if left < right:

D. while left < right:

Solution

1. Step 1: Identify binary search loop condition

   Binary search typically uses while left < right: to narrow down the search space until left meets right.

2. Step 2: Compare options

   while left <= right: is common in classic binary search but for peak finding, while left < right: is preferred to avoid infinite loops.

3. Final Answer:

   while left < right: -> Option D

4. Quick Check:

   Binary search loop uses < not <= [OK]

Hint: Use while left < right for peak element binary search [OK]

Common Mistakes:

• Using for loop instead of while
• Using <= which may cause infinite loop
• Using if instead of loop

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

medium

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Identify peak candidates

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

2. Step 2: Binary search logic

   Binary search will find index 2 by comparing mid elements and moving left or right accordingly.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Peak at index 2 with value 20 [OK]

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

Common Mistakes:

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

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

def find_peak(nums):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < nums[mid + 1]:
            left = mid + 1
        else:
            right = mid - 1
    return left

medium

A. Index mid + 1 may cause out of range error

B. Return should be right instead of left

C. Loop condition should be while left < right

D. Mid calculation is incorrect

Solution

1. Step 1: Check index usage in condition

   The code accesses nums[mid + 1] without checking if mid + 1 is within array bounds.

2. Step 2: Identify potential error

   If mid is at the last index, mid + 1 causes an out of range error.

3. Final Answer:

   Index mid + 1 may cause out of range error -> Option A

4. Quick Check:

   Accessing nums[mid + 1] risks out of range [OK]

Hint: Check array bounds before accessing mid+1 [OK]

Common Mistakes:

• Ignoring array boundary checks
• Using <= in loop causing infinite loop
• Returning wrong index

5. You have an array nums = [10, 20, 15, 2, 23, 90, 67]. Using binary search, which index will be returned as a peak element? Consider multiple peaks exist.

hard

A. 1

B. 4

C. 5

D. 6

Solution

1. Step 1: Identify all peak elements

   Peaks are at index 1 (20 > 10 and 15), index 5 (90 > 23 and 67).

2. Step 2: Understand binary search behavior

   Binary search may return any peak, but typically it finds the one in the middle or right side depending on comparisons.

3. Step 3: Trace binary search on given array

   Mid starts near center; since nums[mid] < nums[mid+1] at some point, search moves right, finally returning index 5.

4. Final Answer:

   5 -> Option C

5. Quick Check:

   Binary search finds peak at index 5 with value 90 [OK]

Hint: Binary search may return any peak; here index 5 is found [OK]

Common Mistakes:

• Assuming only first peak is returned
• Ignoring binary search direction logic
• Confusing index with value