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

↓

Repeat until 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, narrowing down to a peak.

Execution Sample

DSA C#

int FindPeakElement(int[] nums) {
  int low = 0, high = nums.Length - 1;
  while (low < high) {
    int 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 mid+1.

Execution Table

Step	Operation	low	high	mid	nums[mid]	nums[mid+1]	Condition (nums[mid]<nums[mid+1])	Action	Visual State (Array with low, mid, high)
1	Initialize	0	5	-	-	-	-	Start loop	[1, 3, 20, 4, 1, 0] low=0 high=5
2	Calculate mid	0	5	2	20	4	False	high = mid	[1, 3, 20, 4, 1, 0] low=0 mid=2 high=5
3	Calculate mid	0	2	1	3	20	True	low = mid + 1	[1, 3, 20, 4, 1, 0] low=1 mid=1 high=2
4	Calculate mid	1	2	1	3	20	True	low = mid + 1	[1, 3, 20, 4, 1, 0] low=2 mid=1 high=2
5	Calculate mid	2	2	2	20	4	False	high = mid	[1, 3, 20, 4, 1, 0] low=2 mid=2 high=2
6	Loop ends	2	2	-	-	-	-	low == high, return low	[1, 3, 20, 4, 1, 0] peak index=2

💡 Loop ends when low equals high, which is the peak element index.

Variable Tracker

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

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 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.

Why does the loop stop when low equals high?

When low equals high, it means we have narrowed down to one element which is a peak. This is the exit condition shown in execution_table row 6.

What happens if the array has multiple peaks?

The binary search will find any one peak, not necessarily the first or last. The logic ensures the returned index is a valid peak, as seen in the final step.

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 3

C Step 2

D Step 1

💡 Hint

Look at the 'Condition' column in execution_table to find the first 'False'.

If the array was strictly increasing, how would the 'low' pointer move?

A It would move towards the end of the array

B It would stay at 0

C It would move towards the start of the array

D It would jump randomly

💡 Hint

Refer to the logic where if nums[mid] < nums[mid+1], low moves to mid + 1.

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 low to mid+1
  - Else move high to mid
- When low == high, return low as peak index
- Works because peak must exist where nums[mid] >= neighbors

Full Transcript

This concept finds a peak element index in an array using binary search. We start with low at 0 and high at the last index. We calculate mid as the middle index. We compare the element at mid with the element at mid+1. If nums[mid] is less than nums[mid+1], it means the peak is to the right, so we move low to mid+1. Otherwise, the peak is at mid or to the left, so we move high to mid. We repeat this until low equals high. At that point, low is the index of a peak element. This method efficiently narrows down the search space by half each time, ensuring O(log n) time complexity. The execution table shows step-by-step how low, high, and mid change, and how the condition guides the search. The variable tracker shows the values of low, high, and mid after each step. Key moments clarify why we compare with mid+1 and why the loop stops when low equals high. The visual quiz tests understanding of pointer movements and conditions during the search.

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 smaller than its neighbors

C. An element that is greater than its neighbors

D. The last element of the array

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 the search direction.

3. Final Answer:

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

4. Quick Check:

   Peak element = greater than neighbors [OK]

Hint: Peak element > neighbors, use binary search to find it fast [OK]

Common Mistakes:

• Confusing peak with minimum element
• Thinking peak must be at array ends
• Assuming peak equals maximum element in array

2. Which of the following is the correct C# syntax to calculate the middle index in binary search to avoid overflow?

easy

A. int mid = (low + high) / 2;

B. int mid = (high - low) / 2 + high;

C. int mid = (low - high) / 2;

D. int mid = low + (high - low) / 2;

Solution

1. Step 1: Understand overflow risk in mid calculation

   Using (low + high) / 2 can overflow if low and high are large integers.

2. Step 2: Use safe calculation to avoid overflow

   Calculate mid as low + (high - low) / 2 to prevent overflow.

3. Final Answer:

   int mid = low + (high - low) / 2; -> Option D

4. Quick Check:

   Safe mid calculation = low + (high - low) / 2 [OK]

Hint: Use low + (high - low) / 2 to avoid overflow [OK]

Common Mistakes:

• Using (low + high) / 2 causing overflow
• Subtracting incorrectly in mid calculation
• Mixing up low and high in formula

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

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Identify peak candidates in the array

   Array: [1, 3, 20, 4, 1, 0]. 20 at index 2 is greater than neighbors 3 and 4.

2. Step 2: Binary search finds peak at index 2

   Binary search compares mid elements and narrows down to index 2 as peak.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Peak element index = 2 [OK]

Hint: Peak is local max; check neighbors to confirm [OK]

Common Mistakes:

• Choosing first or last element incorrectly
• Confusing peak with global max
• Not checking both neighbors

4. Identify the error in this C# binary search code snippet for finding a peak element:

int mid = low + (high - low) / 2;
if (arr[mid] < arr[mid + 1])
    low = mid + 1;
else
    high = mid - 1;

medium

A. It may cause index out of range when mid is at the last element

B. The mid calculation can overflow

C. The condition should be arr[mid] > arr[mid + 1]

D. The else block should set low = mid + 1

Solution

1. Step 1: Check boundary conditions for arr[mid + 1]

   If mid is the last index, arr[mid + 1] causes index out of range error.

2. Step 2: Need to ensure mid + 1 is within array bounds

   Code must check or limit mid to avoid accessing beyond array length.

3. Final Answer:

   It may cause index out of range when mid is at the last element -> Option A

4. Quick Check:

   Check array bounds before accessing mid+1 [OK]

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

Common Mistakes:

• Ignoring array boundary causing runtime errors
• Incorrect mid calculation causing overflow
• Wrong comparison direction in if condition

5. Given a mountain array [0, 2, 4, 7, 5, 3, 1], which modification to the binary search algorithm helps find the peak element efficiently?

hard

A. Compare mid with mid+1 and move low or high accordingly

B. Always move low to mid+1 regardless of comparison

C. Use linear search instead of binary search

D. Compare mid with mid-1 and move high to mid-1 always

Solution

1. Step 1: Understand mountain array property

   Mountain array increases then decreases, so peak is where arr[mid] > arr[mid+1].

2. Step 2: Use binary search comparing mid and mid+1

   If arr[mid] < arr[mid+1], move low to mid+1; else move high to mid to find peak.

3. Final Answer:

   Compare mid with mid+1 and move low or high accordingly -> Option A

4. Quick Check:

   Compare mid and mid+1 to find peak [OK]

Hint: Compare mid and mid+1 to decide search direction [OK]

Common Mistakes:

• Moving pointers incorrectly ignoring array shape
• Using linear search losing binary search efficiency
• Comparing mid with mid-1 incorrectly