Find Peak Element Using Binary Search in DSA Python

Mental Model

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

Analogy: Imagine climbing a mountain range where you can only see the peak if you stand on a point higher than the points next to it. You check the middle point and decide to go left or right depending on which side is higher, quickly finding a peak without climbing every hill.

Index: 0   1   2   3   4   5   6
Value: 1 -> 3 -> 20 -> 4 -> 1 -> 0 -> 5
          ↑
       mid pointer

Dry Run Walkthrough

Input: array: [1, 3, 20, 4, 1, 0, 5]

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

Step 1: Calculate mid index as 3, check element 4 and its right neighbor 1

Array: 1 -> 3 -> 20 -> [4↑] -> 1 -> 0 -> 5

Why: We check mid to decide which half to search next

Step 2: Since 4 > 1 (right neighbor), move search to left half including mid

Search range: indices 0 to 3
Array: 1 -> 3 -> 20 -> [4↑] -> 1 -> 0 -> 5

Why: Peak must be on left side or at mid because right neighbor is smaller

Step 3: Calculate new mid as 1, check element 3 and its right neighbor 20

Array: 1 -> [3↑] -> 20 -> 4 -> 1 -> 0 -> 5

Why: Check middle of new search range to decide direction

Step 4: Since 3 < 20 (right neighbor), move search to right half excluding mid

Search range: indices 2 to 3
Array: 1 -> 3 -> [20↑] -> 4 -> 1 -> 0 -> 5

Why: Peak must be on right side because right neighbor is bigger

Step 5: Calculate new mid as 2, check element 20 and neighbors 3 and 4

Array: 1 -> 3 -> [20↑] -> 4 -> 1 -> 0 -> 5

Why: Check if mid is peak by comparing neighbors

Step 6: 20 is greater than both neighbors 3 and 4, found peak at index 2

Peak element: 20 at index 2

Why: Peak condition satisfied, stop search

Result:

1 -> 3 -> [20↑] -> 4 -> 1 -> 0 -> 5
Peak element index: 2

Annotated Code

DSA Python

from typing import List

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            # Compare mid element with its right neighbor
            if nums[mid] > nums[mid + 1]:
                # Peak is in left half including mid
                right = mid
            else:
                # Peak is in right half excluding mid
                left = mid + 1
        return left

# Driver code
nums = [1, 3, 20, 4, 1, 0, 5]
sol = Solution()
peak_index = sol.findPeakElement(nums)
print(f"{nums[peak_index]} at index {peak_index}")

while left < right:

loop until search range narrows to one element

mid = (left + right) // 2

find middle index of current search range

if nums[mid] > nums[mid + 1]:

compare mid element with right neighbor to decide direction

right = mid

move right pointer to mid because peak is on left side or at mid

left = mid + 1

move left pointer past mid because peak is on right side

return left

left and right converge to peak element index

Output

20 at index 2

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

Single element array

Returns index 0 as the peak since it's the only element

DSA Python

left, right = 0, len(nums) - 1

Strictly increasing array

Returns last index as peak because last element is greater than previous

DSA Python

left = mid + 1

Strictly decreasing array

Returns first index as peak because first element is greater than next

DSA Python

right = mid

When to Use This Pattern

When asked to find a peak or local maximum in an unsorted array efficiently, use binary search by comparing mid element with neighbors to reduce search space quickly.

Common Mistakes

Mistake: Comparing mid element with left neighbor instead of right neighbor
Fix: Always compare mid with mid+1 to decide which half contains a peak

Mistake: Using <= instead of < in while loop causing infinite loop
Fix: Use while left < right to ensure loop ends when pointers meet

Summary

Finds an index of a peak element where the element is greater than its neighbors.

Use when you need to find a local maximum quickly without scanning the whole array.

The key insight is comparing mid 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. The first element of the array

B. An element that is greater than its neighbors

C. The smallest element in 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 goal

   Binary search finds such an element by comparing middle elements with neighbors to decide search direction.

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:

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

easy

A. while left <= right:

B. for i in nums:

C. if left < right:

D. while left < right:

Solution

1. Step 1: Identify binary search loop condition

   Binary search typically uses while left < right: to narrow down the search space until left meets right.

2. Step 2: Compare options

   while left <= right: is common in classic binary search but for peak finding, while left < right: is preferred to avoid infinite loops.

3. Final Answer:

   while left < right: -> Option D

4. Quick Check:

   Binary search loop uses < not <= [OK]

Hint: Use while left < right for peak element binary search [OK]

Common Mistakes:

• Using for loop instead of while
• Using <= which may cause infinite loop
• Using if instead of loop

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

medium

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Identify peak candidates

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

2. Step 2: Binary search logic

   Binary search will find index 2 by comparing mid elements and moving left or right accordingly.

3. Final Answer:

   2 -> Option A

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

def find_peak(nums):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < nums[mid + 1]:
            left = mid + 1
        else:
            right = mid - 1
    return left

medium

A. Index mid + 1 may cause out of range error

B. Return should be right instead of left

C. Loop condition should be while left < right

D. Mid calculation is incorrect

Solution

1. Step 1: Check index usage in condition

   The code accesses nums[mid + 1] without checking if mid + 1 is within array bounds.

2. Step 2: Identify potential error

   If mid is at the last index, mid + 1 causes an out of range error.

3. Final Answer:

   Index mid + 1 may cause out of range error -> Option A

4. Quick Check:

   Accessing nums[mid + 1] risks out of range [OK]

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

Common Mistakes:

• Ignoring array boundary checks
• Using <= in loop causing infinite loop
• Returning wrong index

5. You have an array nums = [10, 20, 15, 2, 23, 90, 67]. Using binary search, which index will be returned as a peak element? Consider multiple peaks exist.

hard

A. 1

B. 4

C. 5

D. 6

Solution

1. Step 1: Identify all peak elements

   Peaks are at index 1 (20 > 10 and 15), index 5 (90 > 23 and 67).

2. Step 2: Understand binary search behavior

   Binary search may return any peak, but typically it finds the one in the middle or right side depending on comparisons.

3. Step 3: Trace binary search on given array

   Mid starts near center; since nums[mid] < nums[mid+1] at some point, search moves right, finally returning index 5.

4. Final Answer:

   5 -> Option C

5. Quick Check:

   Binary search finds peak at index 5 with value 90 [OK]

Hint: Binary search may return any peak; here index 5 is found [OK]

Common Mistakes:

• Assuming only first peak is returned
• Ignoring binary search direction logic
• Confusing index with value