Leetcode discuss: 162. Find Peak Element

March 8, 2022

Here is the link. 

C# | Binary search algorithm | Learn from my failure

March 7, 2022
Introduction
I spent 20 minutes to try to write my own code using binary search. I could not simplify and make it work. I like to look into this issue quickly and write down some notes.

Binary search
How to design a binary search algorithm to find one of peeks in less than 10 minutes?
Here are facts or tips to review:

1. If there is one element in the binary search, which should be a peek;
2. Minimum case has two elements. Choose middle to be a smaller one if there only is two numbers;
3. Compare middle and middle + 1;
4. Do not compare middle with middle - 1 if left exists; It should be covered in step 3.
5. Do not consider if the middle is the first position of the array, which should be covered in step 3 as well.
6. Do not consider if the middle is the last position of the array, since middle is the smaller if there are only two numbers. Middle cannot be the last position in the array.
7. Always consider middle, not start, not end;
8. Stay focus on two elements and comparison of two integers.
9. It is defined in the problem that any two values in the array next to each other should have different value.

Follow up
March 8, 2022
Reasons for failure
I do think that taking risk and avoid redundant work is so challenge in terms of find a working and simple solution using binary search. I did spend over 20 minutes to write before I could come out a simple solution to compare two numbers, and also limit to only one comparison.

My ideas were so complex, I tried to discuss middle value with right side and also left side, edge cases like two nodes, three nodes etc.

This practice allows me to find my weakness in my analysis. I just love this algorithm.

The following code passes online judge.

public class Solution {
    public int FindPeakElement(int[] nums) {
        var length = nums.Length;
            if (length == 1)
                return 0;

            var start = 0;
            var end = length - 1;            

            while (start < end)
            {
                var middle = start + (end - start) / 2;  // middle is close to start                    

                // argue that middle + 1 is in the range
                if (nums[middle] < nums[middle + 1]) // middle is not a peak
                {
                    start = middle + 1;
                }
                else
                {
                    end = middle; // middle maybe is a peak
                }
            }

            return start;
    }
}