Find Peak Element

Problem: 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.

Example:

Input: nums = [2,4,2,3,4,9,8]
Output: 1 or 5 
Explanation: Either index 1 where the peak element is 4 or index 5 where the peak element is 9.

Approach: Straightforward solution is to traverse each element just check the condition arr[i - 1] < arr[i] > arr[i + 1] and we are done but it will take O(n) time. We can do it in O(logn) using the binary search approach:

1. IF arr[mid] > arr[mid + 1] then we know that we need to look at the left array partition including mid.
2. ELSE we need to look at right subarray. 

Implementation in C#:

        public int FindPeakElement(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return -1;

        }

        if (length == 1 || nums[0] > nums[1])

        {

            return 0;

        }

        if (nums[length - 1] > nums[length - 2])

        {

            return length - 1;

        }

        int start = 1, end = length - 2;

        while (start <= end)

        {

            int mid = start + (end - start) / 2;

            if (nums[mid] > nums[mid - 1] &&

                nums[mid] > nums[mid + 1])

            {

                return mid;

            }

            else if (nums[mid] <= nums[mid + 1])

            {

                start = mid + 1;

            }

            else

            {

                end = mid - 1;

            }

        }

        return -1;

    }

Complexity: O(logn)