DSA sheet · Binary Search · Classic pattern (last problem)

Find Peak Element

Find any index whose value is bigger than both its neighbours, in O(log n), on an array that is not sorted. The teacher shows that binary search still works, because comparing nums[mid] with one neighbour tells us which side is guaranteed to have a peak. She then solves it two ways: leaning left and leaning right. The second way gets a TLE (time limit exceeded) on screen, and she fixes it by picking the second middle. That fix is the real lesson of this video.

Why it matters: it proves binary search needs a reliable yes/no direction, not a sorted array. It also teaches the most common binary search bug: an endless loop when you write left = mid.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: check every index
• Part B · Binary search leaning left (compare with mid + 1)
• Part C · Binary search leaning right (compare with mid − 1), the TLE and its fix
• Part D · Revision page

Part 0 · Before starting

Why binary search works (and why it doesn't need a sorted array)

Binary search checks the middle and then throws away half of the range. All it needs is a test at mid that tells us, for sure, "an answer exists on this side". Sorted arrays give us such a test easily, but they're not the only way. In this problem the test is "is nums[mid] bigger than its right neighbour?" As we'll see, either answer points to a side where a peak is guaranteed.

left, right, mid

• left starts at 0, right at n − 1: the range where we still look for a peak.
• mid = left + (right - left) // 2. The teacher repeats the reason: in Java/C++, left + right could go past the int limit when both are huge and turn negative. Here n ≤ 1000, so the plain form would work, but the safe form is the habit. Python ints never overflow anyway.
• When the range has an even number of cells, there are two middles. left + (right - left) // 2 picks the first (lower) one, and left + (right - left + 1) // 2 picks the second (upper) one. This tiny difference is the whole of Part C.

index:  0  1  2  3          left = 0, right = 3: two middles
value:  1  2  3  1
           ↑  ↑
   first mid  second mid
   0 + 3//2 = 1   0 + (3+1)//2 = 2

What is a peak?

An element is a peak if it is strictly greater than its left neighbour and its right neighbour. For the first and last elements, the missing neighbour counts as −∞ (minus infinity), so an edge element only has to beat its one real neighbour. (LeetCode states this as nums[-1] = nums[n] = -∞.)

Part A · Brute force: check every index

LeetCode 162

1The question in simple words

Given nums, return the index of any peak. If there are several peaks, any one of them is accepted.

In the second array, 2 beats 1 and 1. And 6 beats 5 and 4. The 5 is not a peak (5 > 3 but 5 < 6).

2What the constraints tell us

• Length 1 to 1000 → n is small, so a plain O(n) loop would pass. If n were around 10⁹, O(n) would TLE. The problem anyway says "must run in O(log n)", so it wants binary search.
• Values span the full 32-bit range (−2³¹ to 2³¹ − 1) → we only compare values and never add them, so nothing can overflow.
• nums[i] != nums[i + 1] → no two neighbours are equal. So between two neighbours it's always strictly up or strictly down. This is what makes the binary search direction reliable.

3Intuition

Walk through the array and, at each index, ask: "am I bigger than the left neighbour and the right neighbour?" The first index that says yes is a peak.

4Building the check

The teacher starts the loop at index 1 and checks nums[i-1] and nums[i+1]. On [1,2,3,1]: index 1 (2) beats 1 but not 3 ✗. Index 2 (3) beats 2 and 1 ✓ → return 2.

5Approach steps

1. For each index i: left_val = nums[i-1], or −∞ if i = 0. right_val = nums[i+1], or −∞ if i = n − 1.
2. If nums[i] is bigger than both → return i.

6Code (Python)

class Solution:
    def findPeakElement(self, nums):
        n = len(nums)
        for i in range(n):
            left_val = nums[i - 1] if i > 0 else float('-inf')
            right_val = nums[i + 1] if i < n - 1 else float('-inf')
            if nums[i] > left_val and nums[i] > right_val:
                return i
        return -1   # never reached: a peak always exists

7Code line by line

8Dry run

[1,2,1,3,5,6,4]: i = 0: 1 > −∞ but 1 < 2 ✗ · i = 1: 2 > 1 and 2 > 1 ✓ → return 1. (A linear scan always finds the leftmost peak.)

9Complexity & remember

• Time O(n), space O(1). Fine for n = 1000, but not the O(log n) the problem asks for.

Part B · Binary search leaning left (compare with mid + 1)

1The question (same as Part A)

Return any peak index, in O(log n).

2What the constraints tell us

• No equal neighbours → nums[mid] vs nums[mid+1] is always strictly > or <. There's no "flat" case to handle.
• "Return any peak" → we don't need a specific peak. We only need a side that surely has one. This freedom is what lets us throw half away.

3Intuition: think of a mountain

The teacher's observation: if the array has only one peak, everything to the left of it goes up (sorted ascending), and everything to its right goes down (sorted descending). Like a mountain:

            6
          5   4             values 1 3 5 6 4 2
        3       2           left of 6: going up   (ascending)
      1                     right of 6: going down (descending)

With several peaks there are several hills, so the array isn't "two sorted halves" any more. But the local idea still holds. Stand at mid and look at the next cell:

• Next cell is lower (nums[mid] > nums[mid+1]): you're on a downhill slope going right. Walk left from mid: either the values keep rising until a cell that's bigger than its left neighbour (a peak), or you reach index 0, which beats its −∞ neighbour (also a peak). Either way, a peak exists at mid or to its left. Mid itself could be that peak.
• Next cell is higher (nums[mid] < nums[mid+1]): you're going uphill to the right. Mid is not a peak (it loses to mid + 1). Walk right from mid + 1 and you're guaranteed to reach a top. So a peak exists in mid + 1 … right.

4Building the conditions from examples

Example 1: mid is bigger than mid + 1, but mid is NOT a peak

index:   0   1   2   3   4   5   6
value:   2   7   5  [4]  3   9   8
                     M
nums[3] = 4  >  nums[4] = 3     → downhill to the right

4 beats its right neighbour, but it isn't a peak (4 < 5 on its left). Still, we're sure there's a peak at index 3 or to its left: walking left, 4 → 5 → 7, and 7 beats 2 and 5. So we search left..mid.

Notice there's also a peak on the right (9, at index 5). The teacher's point: she isn't saying "there's no peak on the right". She's saying "there's surely one on the left", and that's enough.

Rule: right = mid when going left, left = mid + 1 otherwise

• nums[mid] > nums[mid+1] → the peak is at mid or to its left. Mid might be the answer, so don't drop it: right = mid (not mid - 1).
• Otherwise → mid loses to mid + 1, so it's surely not a peak: left = mid + 1.

The loop: while left < right

We stop when left and right meet. A peak is always kept inside left..right, so the single cell left must be a peak. Return left (or right, same index; the teacher shows both pass).

5Approach steps

1. left = 0, right = n - 1.
2. While left < right: mid = left + (right - left) // 2 (first middle).
3. If nums[mid] > nums[mid + 1] → right = mid.
4. Else → left = mid + 1.
5. Return left.

6Code (Python)

class Solution:
    def findPeakElement(self, nums):
        left, right = 0, len(nums) - 1

        while left < right:
            mid = left + (right - left) // 2      # first middle

            if nums[mid] > nums[mid + 1]:         # downhill: peak at mid or left
                right = mid                       # mid may be the peak, keep it
            else:                                 # uphill: peak to the right
                left = mid + 1                    # mid is surely not a peak

        return left                               # left == right

7Code line by line

8Dry run

Run 1: [1,2,1,3,5,6,4]

The peak at index 1 was thrown away in step 1. That's fine: the problem accepts any peak.

Run 2: [1,2,3,1]

l 0, r 3, mid 1: 2 < 3 → left = 2 · l 2, r 3, mid 2: 3 > 1 → right = 2 · return 2 ✓

Run 3: [6,5,4,3,9,8] (peak at the left edge)

mid 2: 4 > 3 → right = 2 · mid 1: 5 > 4 → right = 1 · mid 0: 6 > 5 → right = 0 · return 0 ✓

9Complexity & remember

• Time O(log n): half the range is dropped each step.
• Space O(1).

Part C · Binary search leaning right (compare with mid − 1), the TLE and its fix

Since any peak is fine, the teacher flips the idea: compare mid with its left neighbour and lean right. Steps 1–2 are the same as Part B. What changes is the condition, the pointer moves, and (after a TLE) the choice of mid.

3Intuition

• nums[mid] > nums[mid-1]: coming from the left we went up into mid. Walk right from mid: either it keeps rising until the right edge (which beats −∞), or it drops somewhere, and the cell just before the drop is a peak. So a peak is at mid or to its right → left = mid (keep mid).
• Otherwise mid loses to mid − 1 → mid isn't a peak, and there's surely one on the left → right = mid - 1.

Looking right first, you check the left neighbour. Looking left first (Part B), you check the right neighbour.

4The first attempt, and why it gets TLE

class Solution:
    def findPeakElement(self, nums):
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2      # first middle: the bug
            if nums[mid] > nums[mid - 1]:
                left = mid
            else:
                right = mid - 1
        return left

On [1,2,3,1]:

When only two cells are left (left = 2, right = 3), the first middle is left. Setting left = mid doesn't move anything, so the loop never ends.

On some arrays the loop happens to end through the right = mid - 1 branch before this two-cell trap, which is why the bug can hide until a test case like this one hits it.

The fix: take the SECOND middle

The teacher's fix: when the range has two middles, pick the second (upper) one. Add 1 before halving:

mid = left + (right - left + 1) // 2      # second middle

Now with left = 2, right = 3: mid = 2 + (1 + 1) // 2 = 3. Either left = 3 (the range closes) or right = 2 (the range closes). Progress every time.

5Approach steps

1. left = 0, right = n - 1.
2. While left < right: mid = left + (right - left + 1) // 2 (second middle).
3. If nums[mid] > nums[mid - 1] → left = mid.
4. Else → right = mid - 1.
5. Return left.

6Code (Python)

class Solution:
    def findPeakElement(self, nums):
        left, right = 0, len(nums) - 1

        while left < right:
            mid = left + (right - left + 1) // 2  # SECOND middle

            if nums[mid] > nums[mid - 1]:         # came uphill into mid
                left = mid                        # peak at mid or right, keep mid
            else:                                 # mid lost to its left neighbour
                right = mid - 1                   # peak surely on the left

        return left

7Code line by line (what differs from Part B)

8Dry run

Run 1: [1,2,3,1], the array that froze before

Run 2: [1,2,1,3,5,6,4]

9Complexity, the teacher's advice & remember

• Time O(log n), space O(1), same as Part B.

The teacher's advice: for every binary search problem, write it both ways (lean left and lean right). When one way breaks, work out why. Here, doing that is how you discover the "second middle" rule. An educator can't show every variation in one video, so trying the other direction yourself and debugging it is how you really learn.

Part D · Revision page

s = Solution()
print(s.findPeakElement([1, 2, 3, 1]))            # 2
print(s.findPeakElement([1, 2, 1, 3, 5, 6, 4]))   # 1 or 5 (both are peaks)
print(s.findPeakElement([6, 5, 4, 3, 9, 8]))      # 0 or 4
print(s.findPeakElement([7]))                     # 0

Based on this video: Find Peak Element