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

↓

Done

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

Execution Sample

DSA Java

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]	Pointer Change	Visual State
1	Initialize low and high	0	5	-	-	-	low=0, high=5	[1, 3, 20, 4, 1, 0]
2	Calculate mid	0	5	2	20	4	-	[1, 3, 20, 4, 1, 0]
3	Compare nums[mid] < nums[mid+1]	0	5	2	20	4	No, high=mid=2	[1, 3, 20, 4, 1, 0]
4	Calculate mid	0	2	1	3	20	-	[1, 3, 20, 4, 1, 0]
5	Compare nums[mid] < nums[mid+1]	0	2	1	3	20	Yes, low=mid+1=2	[1, 3, 20, 4, 1, 0]
6	Calculate mid	2	2	2	20	-	-	[1, 3, 20, 4, 1, 0]
7	Compare nums[mid] < nums[mid+1]	2	2	2	20	-	No change	[1, 3, 20, 4, 1, 0]
8	low == high, return low	2	2	-	-	-	Return 2	[1, 3, 20, 4, 1, 0]

💡 low equals high at index 2, which is a peak element.

Variable Tracker

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

Key Moments - 3 Insights

Why do we compare nums[mid] with nums[mid+1] and not nums[mid-1]?

Because the code always moves low or high based on the comparison with nums[mid+1], ensuring the search space moves towards a peak. This is shown in execution_table rows 3 and 5 where the decision depends on nums[mid+1].

Why does the loop stop when low equals high?

When low equals high, it means the search space has narrowed down to one element, which must be a peak. This is shown in execution_table row 8 where low=high=2 and the function returns.

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 a peak is found by moving towards a higher neighbor, as seen in the pointer changes in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the value of low after the operation?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Pointer Change' column at Step 5 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 5

B Step 3

C Step 7

D Step 2

💡 Hint

Look at the 'Compare nums[mid] < nums[mid+1]' column and see when the pointer change is 'No'.

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, low moves up to mid+1 repeatedly until it reaches the last index, as shown in the variable_tracker for low.

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
- Works because peak must exist and search space shrinks each step

Full Transcript

This visualization 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. This narrows the search space until low equals high, which is the peak index. The execution table traces each step with pointer changes and array values. Key moments clarify why we compare with nums[mid+1], why the loop stops when low equals high, and how multiple peaks are handled. The quiz tests understanding of pointer updates 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 smallest element in the array

B. An element that is greater than its neighbors

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: Relate to binary search usage

   Binary search finds such an element by comparing mid elements with neighbors to decide which half to search next.

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:

• Confusing peak with minimum element
• Thinking peak must be at array ends only
• Assuming peak equals neighbors

2. Which of the following is the correct way to start the binary search for a peak element in Java?

easy

A. int left = 0, right = arr.length;

B. int left = 1, right = arr.length;

C. int left = 0, right = arr.length - 1;

D. int left = 1, right = arr.length - 1;

Solution

1. Step 1: Identify valid index range for binary search

   Array indices in Java go from 0 to length-1, so left should be 0 and right should be arr.length - 1.

2. Step 2: Check options for correct initialization

   int left = 0, right = arr.length - 1; correctly sets left=0 and right=arr.length-1, which covers the whole array.

3. Final Answer:

   int left = 0, right = arr.length - 1; -> Option C

4. Quick Check:

   Index range = 0 to length-1 [OK]

Hint: Array indices start at 0, end at length-1 [OK]

Common Mistakes:

• Starting right at arr.length causes out-of-bounds
• Starting left at 1 skips first element
• Using invalid index ranges

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

B. 1

C. 3

D. 2

Solution

1. Step 1: Identify peak elements in the array

   Array: [1, 3, 20, 4, 1, 0]. 20 at index 2 is greater than neighbors 3 and 4, so it's a peak.

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

   Binary search compares mid elements and moves left or right until it finds 20 at index 2.

3. Final Answer:

   2 -> Option D

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
• Ignoring neighbors comparison

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

int mid = left + (right - left) / 2;
if (arr[mid] < arr[mid + 1]) {
    left = mid + 1;
} else {
    right = mid - 1;
}
return left;

medium

A. It may cause ArrayIndexOutOfBoundsException at arr[mid + 1]

B. It returns right instead of left

C. It uses wrong mid calculation causing infinite loop

D. It should compare arr[mid] with arr[mid - 1]

Solution

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

   If mid is at the last index, arr[mid + 1] access causes ArrayIndexOutOfBoundsException.

2. Step 2: Identify missing boundary check

   The code does not check if mid + 1 is within array bounds before accessing.

3. Final Answer:

   It may cause ArrayIndexOutOfBoundsException at arr[mid + 1] -> Option A

4. Quick Check:

   Accessing arr[mid+1] at end causes error [OK]

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

Common Mistakes:

• Ignoring array boundary checks
• Assuming mid+1 always valid
• Confusing left and right updates

5. You have an array [10, 20, 15, 2, 23, 90, 67]. Using binary search to find a peak element, which index will the algorithm return?

hard

A. 5

B. 6

C. 4

D. 1

Solution

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

   Array: [10, 20, 15, 2, 23, 90, 67]. Peaks are 20 (index 1), 90 (index 5).

2. Step 2: Understand binary search behavior

   Binary search compares mid with neighbors and moves towards the side with higher neighbor. It will find 90 at index 5 as peak.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Peak found at index 5 = 90 [OK]

Hint: Binary search finds any peak, here index 5 with value 90 [OK]

Common Mistakes:

• Assuming only first peak is returned
• Confusing peak with global max
• Not tracing binary search steps carefully