Find Peak Element Using Binary Search in DSA Typescript

Mental Model

A peak element is one that is bigger than its neighbors. We use binary search to quickly find such a peak by checking the middle and deciding which side to search next.

Analogy: Imagine walking on hills and valleys. If you stand somewhere and see the slope going up on one side, you know a peak must be in that direction. You keep moving halfway towards that side until you find the top.

Array: [1, 3, 2, 5, 4]
Indexes:  0  1  2  3  4

Initial search range:
start -> 0
end   -> 4

Middle points to index 2 (value 2)
Neighbors: 3 (left), 5 (right)

Dry Run Walkthrough

Input: array: [1, 3, 2, 5, 4]

Goal: Find any peak element index where element is greater than neighbors

Step 1: Calculate mid = (0 + 4) // 2 = 2; compare nums[2] = 2 with nums[3] = 5

[1, 3, 2, 5, 4]
start=0, end=4, mid=2

Why: We check if right neighbor is bigger to decide search direction

Step 2: Since nums[2] < nums[3], move start to mid + 1 = 3

[1, 3, 2, 5, 4]
start=3, end=4

Why: Peak must be on right side because slope goes up

Step 3: Calculate mid = (3 + 4) // 2 = 3; compare nums[3] = 5 with nums[4] = 4

[1, 3, 2, 5, 4]
start=3, end=4, mid=3

Why: Check if mid is peak by comparing with right neighbor

Step 4: Since nums[3] > nums[4], move end to mid = 3

[1, 3, 2, 5, 4]
start=3, end=3

Why: Peak is at mid or left side because slope goes down on right

Result:

Peak found at index 3 with value 5

Annotated Code

DSA Typescript

class Solution {
  findPeakElement(nums: number[]): number {
    let start = 0
    let end = nums.length - 1

    while (start < end) {
      const mid = Math.floor((start + end) / 2)
      // Compare middle element with its right neighbor
      if (nums[mid] < nums[mid + 1]) {
        // Peak must be on right side
        start = mid + 1
      } else {
        // Peak is at mid or on left side
        end = mid
      }
    }
    // start and end converge to peak index
    return start
  }
}

// Driver code
const solution = new Solution()
const nums = [1, 3, 2, 5, 4]
const peakIndex = solution.findPeakElement(nums)
console.log(`Peak found at index ${peakIndex} with value ${nums[peakIndex]}`)

while (start < end) {

loop until search range narrows to one element

const mid = Math.floor((start + end) / 2)

calculate middle index to check

if (nums[mid] < nums[mid + 1]) {

compare mid element with right neighbor to decide direction

start = mid + 1

move start to right half because slope goes up

end = mid

move end to mid because peak is at mid or left side

return start

start and end converge to peak index

Output

Peak found at index 3 with value 5

Complexity Analysis

Time: O(log n) because binary search halves the search space each step

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear scan O(n), binary search is much faster for large arrays

Edge Cases

Array with single element

Returns index 0 as peak since it has no neighbors

DSA Typescript

while (start < end) {

Strictly increasing array like [1, 2, 3, 4]

Peak is last element; binary search moves right until end

DSA Typescript

if (nums[mid] < nums[mid + 1]) {

Strictly decreasing array like [4, 3, 2, 1]

Peak is first element; binary search moves left until start

DSA Typescript

else { end = mid }

When to Use This Pattern

When you need to find a local maximum in an array quickly, use binary search on neighbors to reduce search space efficiently.

Common Mistakes

Mistake: Comparing mid element with left neighbor instead of right neighbor
Fix: Always compare nums[mid] with nums[mid + 1] to decide direction

Mistake: Using start <= end in loop causing infinite loop
Fix: Use start < end to ensure loop ends when pointers converge

Summary

Finds an index of a peak element where neighbors are smaller.

Use when you want to find a local maximum faster than scanning all elements.

The key insight is comparing middle element with its right neighbor to decide which half contains a peak.

Practice

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

easy

A. An element that is greater than its neighbors

B. The smallest element in the array

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: Apply this to binary search context

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

3. Final Answer:

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

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

easy

A. while(left < right) { ... }

B. if(nums[mid] > nums[mid+1]) { ... }

C. for(let i = 0; i < nums.length; i++)

D. switch(nums[mid]) { ... }

Solution

1. Step 1: Identify the loop type for binary search

   Binary search uses a while loop with condition left < right to narrow down the search range.

2. Step 2: Check options for correct binary search syntax

   while(left < right) { ... } shows the correct while loop structure for binary search.

3. Final Answer:

   while(left < right) { ... } -> Option A

4. Quick Check:

   Binary search uses while loop [OK]

Hint: Binary search uses while(left < right) loop [OK]

Common Mistakes:

• Using for loop instead of while
• Using if instead of loop for search
• Using switch incorrectly for binary search

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

medium

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Identify peak elements in the array

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

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

   Binary search compares mid with neighbors and narrows to index 2.

3. Final Answer:

   2 -> Option C

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 always
• Ignoring neighbors in peak definition

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

let left = 0;
let right = nums.length - 1;
while (left < right) {
  let mid = Math.floor((left + right) / 2);
  if (nums[mid] < nums[mid + 1]) {
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}
return left;

medium

A. Return should be right instead of left

B. The loop condition should be while(left <= right)

C. The mid calculation is incorrect

D. The else branch should set right = mid, not mid - 1

Solution

1. Step 1: Analyze the else branch update of right pointer

   Setting right = mid - 1 skips the mid element, possibly missing peak.

2. Step 2: Correct approach is right = mid to keep mid in range

   To ensure peak is not skipped, right should be set to mid, not mid - 1.

3. Final Answer:

   The else branch should set right = mid, not mid - 1 -> Option D

4. Quick Check:

   Keep mid in range by right = mid [OK]

Hint: Use right = mid to avoid skipping mid element [OK]

Common Mistakes:

• Setting right = mid - 1 causing missed peaks
• Changing loop condition unnecessarily
• Miscomputing mid index

5. You have an array nums = [10, 20, 15, 2, 23, 90, 67]. Using binary search to find a peak element, which index could be returned as a valid peak?

hard

A. 2

B. 5

C. 6

D. 3

Solution

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

   Peaks are elements greater than neighbors: 20 at index 1 and 90 at index 5.

2. Step 2: Binary search can return any peak; index 5 (value 90) is a valid peak

   90 is greater than 23 and 67, so index 5 is a valid peak.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   90 at index 5 is peak [OK]

Hint: Binary search may return any peak, here index 5 is valid [OK]

Common Mistakes:

• Assuming only one peak exists
• Choosing non-peak elements
• Ignoring neighbors when checking peak