Find Peak Element Using Binary Search in DSA Go - Build from Scratch

Find Peak Element Using Binary Search

📖 Scenario: You are working with a list of numbers representing heights of hills along a trail. You want to find a hill that is taller than its neighbors, called a peak.Using a fast method called binary search, you will find one peak hill without checking every hill.

🎯 Goal: Build a Go program that finds a peak element in a list of integers using binary search.A peak element is one that is greater than its neighbors.

📋 What You'll Learn

Create a slice of integers called heights with the exact values: 1, 3, 20, 4, 1, 0

Create two integer variables left and right to hold the start and end indexes of the slice

Write a for loop that runs while left is less than right

Inside the loop, calculate the middle index mid and compare heights[mid] with heights[mid+1]

Adjust left or right based on the comparison to narrow down the peak location

After the loop ends, print the index of the peak element

💡 Why This Matters

🌍 Real World

Finding peak elements quickly is useful in signal processing, stock price analysis, and terrain mapping where you want to identify local maximum points.

💼 Career

Binary search and peak finding algorithms are common in software engineering interviews and are useful for optimizing search problems in real applications.

1

Create the heights slice

Create a slice of integers called heights with these exact values: 1, 3, 20, 4, 1, 0

DSA Go

# Create the slice heights with values 1, 3, 20, 4, 1, 0
# Your code here

Hint

Use heights := []int{1, 3, 20, 4, 1, 0} to create the slice.

2

Set left and right pointers

Create two integer variables called left and right. Set left to 0 and right to the last index of heights (which is 5).

DSA Go

package main

func main() {
    heights := []int{1, 3, 20, 4, 1, 0}
    // Create left and right variables
    // Your code here
}

Hint

Use left := 0 and right := len(heights) - 1.

3

Implement binary search loop to find peak

Write a for loop that runs while left < right. Inside the loop, calculate mid as (left + right) / 2. If heights[mid] is less than heights[mid+1], set left to mid + 1. Otherwise, set right to mid.

DSA Go

package main

func main() {
    heights := []int{1, 3, 20, 4, 1, 0}
    left := 0
    right := len(heights) - 1

    // Write a for loop to find the peak
    // Your code here
}

Hint

Use a for loop with condition left < right. Calculate mid inside the loop. Compare heights[mid] and heights[mid+1] to decide how to move left or right.

4

Print the peak element index

Print the value of left which is the index of the peak element.

DSA Go

package main

import "fmt"

func main() {
    heights := []int{1, 3, 20, 4, 1, 0}
    left := 0
    right := len(heights) - 1

    for left < right {
        mid := (left + right) / 2
        if heights[mid] < heights[mid+1] {
            left = mid + 1
        } else {
            right = mid
        }
    }

    // Print the peak index
    // Your code here
}

Hint

Use fmt.Println(left) to print the peak index.

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. An element that is smaller than its neighbors

C. The first element of the array

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 only one side if at the boundary).

2. Step 2: Apply this to binary search context

   Binary search finds such an element by comparing middle elements 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 smaller [OK]

Common Mistakes:

• Thinking peak is smallest element
• Confusing peak with first or last element always
• Ignoring boundary conditions

2. Which Go code snippet correctly initializes the binary search boundaries to find a peak element in array nums?

easy

A. left, right := 1, len(nums)

B. left, right := 0, len(nums) - 1

C. left, right := 0, len(nums)

D. left, right := 1, len(nums) - 1

Solution

1. Step 1: Identify valid index range for array in Go

   Array indices in Go start at 0 and end at len(nums)-1, so boundaries must be set accordingly.

2. Step 2: Check each option for correct boundary initialization

   left, right := 0, len(nums) - 1 correctly sets left=0 and right=len(nums)-1, covering full array indices.

3. Final Answer:

   left, right := 0, len(nums) - 1 -> Option B

4. Quick Check:

   Array indices 0 to len-1 [OK]

Hint: Array indices go from 0 to length-1 in Go [OK]

Common Mistakes:

• Setting right to len(nums) (out of range)
• Starting left at 1 and missing first element
• Using negative indices

3. What will be the output index of the peak element for the array nums := []int{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 candidates 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: Confirm binary search finds index 2

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

3. Final Answer:

   2 -> Option C

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 the following Go code snippet to find a peak element, what is the bug?

func findPeak(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := (left + right) / 2
        if nums[mid] < nums[mid+1] {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left
}

medium

A. The right boundary update should be right = mid, not mid - 1

B. The left boundary update should be left = mid, not mid + 1

C. The loop condition should be left <= right

D. The function should return right instead of left

Solution

1. Step 1: Analyze the binary search boundary updates

   When nums[mid] >= nums[mid+1], peak is at mid or to the left, so right should be set to mid, not mid - 1 to avoid skipping mid.

2. Step 2: Identify impact of wrong right update

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

3. Final Answer:

   The right boundary update should be right = mid, not mid - 1 -> Option A

4. Quick Check:

   Right boundary must include mid [OK]

Hint: Use right = mid to keep mid in search space [OK]

Common Mistakes:

• Setting right = mid - 1 and skipping mid
• Changing left incorrectly
• Wrong loop condition causing infinite loop

5. You have an array nums := []int{10, 20, 15, 2, 23, 90, 67}. Using binary search to find a peak element, which index will be returned and why?

hard

A. 1, because 20 is a peak greater than neighbors 10 and 15

B. 0, because first element is always a peak

C. 6, because last element is always a peak

D. 5, because 90 is a peak greater than neighbors 23 and 67

Solution

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

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

2. Step 2: Understand binary search behavior

   Binary search compares mid and mid+1; it will move towards the higher peak 90 at index 5.

3. Step 3: Confirm returned index

   Binary search will return index 5 where 90 is a peak greater than neighbors 23 and 67.

4. Final Answer:

   5, because 90 is a peak greater than neighbors 23 and 67 -> Option D

5. Quick Check:

   Binary search finds highest local peak at index 5 [OK]

Hint: Binary search finds any peak, often the higher one found first [OK]

Common Mistakes:

• Assuming first or last element always peak
• Choosing smaller peak incorrectly
• Not understanding binary search direction