Start learning free

LESSON 251 OF 347 · BINARY SEARCH

Find Peak in C#: O(log n) Binary Search on Slopes

Practice O(log n) Read the full explanation

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1, 2, 3, 1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1, 2, 1, 3, 5, 6, 4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

Note:

Your algorithm should run in O(log n) time and use O(1) extra space.


STEP 1 OF 15
    Ctrl + Enter to check

    C# · BINARY SEARCH

    Find Peak in C#, explained

    Problem overview

    FindPeakElement receives an int[] nums in which no two neighbouring values are equal. A peak is an element greater than both of its neighbours, and the method returns the index of any one peak. The positions just outside the array, nums[-1] and nums[n], count as negative infinity. So the first element is a peak if it beats its right neighbour, and the last is a peak if it beats its left one.

    For {1, 2, 3, 1} the answer is 2, the index of the 3. For {1, 2, 1, 3, 5, 6, 4} both index 1 and index 5 are peaks, and either is accepted.

    The lesson asks for O(log n) time and O(1) extra space. A scan from left to right is O(n), so the array has to be halved at every step even though it isn't sorted.

    Approach: follow the slope uphill

    Binary search normally needs sorted data. Here it needs something weaker: a rule that says which half is guaranteed to contain an answer.

    Look at the middle element and its neighbours:

    • If the left neighbour is larger, the values go up toward the left. Walk left while they keep rising and you must stop somewhere: either at a peak, or at the start of the array, which is a peak because nums[-1] is negative infinity. So a peak exists on the left.
    • If the right neighbour is larger, the same argument works toward the right.
    • If neither neighbour is larger, the middle element is itself a peak.

    Each step either finishes or throws away half of the indices, so the search takes O(log n) steps.

    Here is {1, 2, 1, 3, 5, 6, 4} traced. The window is indices 0 to 6, so middle is 3 and the value is 3. The left neighbour, 1, is smaller. The right neighbour, 5, is larger, so the search goes right with left = 4. The window 4 to 6 has middle = 5 and value 6. Both neighbours, 5 and 4, are smaller, so index 5 is returned.

    Step by step

    1. Declare left and right in one int statement, as 0 and nums.Length - 1. A peak can be at any index, so the window starts as the whole array.
    2. Loop while left <= right. Using <= keeps the loop alive when the window has a single index, which may be the peak.
    3. Compute middle as left + (right - left) / 2. Integer division rounds down, and this form never adds the two indices together.
    4. Ask whether going left is justified by calling a helper, CanGoLeft(nums, middle), which is written later.
    5. If so, set right = middle - 1. Because neighbours are never equal in this problem, the left neighbour is greater than nums[middle] in that case, so middle is not a peak and can be dropped with the right half.
    6. Otherwise ask CanGoRight(nums, middle) in an else if, so the search only goes right when going left isn't possible.
    7. If so, set left = middle + 1, which drops middle and everything before it.
    8. Otherwise return middle. Neither side has a larger neighbour, which is the definition of a peak.
    9. Return 0 after the loop. C# demands a return on every path. The loop returns a peak first, so this line is a safety net.
    10. Write CanGoLeft as a public bool method taking nums and an index i.
    11. Handle its boundary. At i == 0 there is nothing on the left, so it returns false.
    12. Otherwise return nums[i - 1] >= nums[i]. A comparison is already a bool, so no if/else is needed.
    13. Write CanGoRight the same way, with the same parameters.
    14. Handle its boundary. At i == nums.Length - 1 it returns false.
    15. Otherwise return nums[i + 1] >= nums[i].

    The solution in C#

    class Solution {

    public bool CanGoRight(int[] nums, int i) {
        if (i == nums.Length - 1) {
            return false;
        }
        return nums[i + 1] >= nums[i];
    }

    public bool CanGoLeft(int[] nums, int i) {
        if (i == 0) {
            return false;
        }
        return nums[i - 1] >= nums[i];
    }

    public int FindPeakElement(int[] nums) {
        int left = 0, right = nums.Length - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (CanGoLeft(nums, middle)) {
                right = middle - 1;
            } else if (CanGoRight(nums, middle)) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return 0;
    }
};

    C# details worth knowing

    • Declaring two variables at once. int left = 0, right = nums.Length - 1; declares two int variables of the same type in one statement.
    • Returning a comparison. The expression nums[i + 1] >= nums[i] has type bool, so return can hand it straight back.
    • Staying in bounds. Each helper checks its boundary first, so the index i - 1 or i + 1 is never read when it would fall outside the array. Reading nums[-1] or nums[nums.Length] throws an IndexOutOfRangeException.
    • Method names. The helpers are CanGoLeft and CanGoRight in PascalCase. C# is case-sensitive, so canGoLeft would be a different, undefined name.
    • The trailing semicolon after the closing brace of the class is allowed in C# and does nothing.

    Complexity

    The window shrinks by about half on each iteration, so there are at most about log₂ n iterations. Each iteration does a constant amount of work: one midpoint, and two helper calls that compare a couple of elements. The time is O(log n).

    Only the variables left, right and middle are stored, so the extra space is O(1).

    Edge cases and common mistakes

    • One element. For {5} the window is just index 0. Both helpers return false because of their boundary checks, so the method returns 0.
    • Peaks at the ends. For {1, 2, 3} the search moves right and returns index 2. The last element is a peak because the position after it counts as negative infinity.
    • Forgetting the boundary checks. Without them, the first and last indices read outside the array.
    • Using left < right. With this solution's updates, middle - 1 and middle + 1, that condition skips the last one-index window, which may hold the only peak. Keep <=.
    • Several valid answers. The method returns one peak, which may not be the first or the largest. For {1, 2, 1, 3, 5, 6, 4} it returns 5, and 1 would be accepted too.
    • Dropping the wrong half. Moving toward the smaller neighbour can leave the window with no peak. Always move toward a larger neighbour.

    Testing

    numsresult
    {1, 2, 3, 1}2
    {1, 2, 1, 3, 5, 6, 4}5
    {5}0
    {1, 2, 3}2
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free