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
Test your understanding
Look at the execution_table at Step 3, what is the value of 'low' after the action?
A0
B1
C2
D3
💡 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?
AStep 4
BStep 2
CStep 3
DStep 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'?
AIt would increase until it equals high
BIt would decrease
CIt would stay the same
DIt 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.