3.Find Peak Element

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

Algorithm:

1. Check if the mid value or index mid = (l+r)/2, is the peak element or not, if yes then print the element and terminate. (check of if both the left and right neighbors are greater)

2. Else if the element on the left side of the middle element is greater then check for peak element on the left side, i.e. update r = mid – 1

3. Else if the element on the right side of the middle element is greater then check for peak element on the right side , i.e. update l = mid + 1

Corner Cases:

1. If input array is sorted in strictly increasing order, the last element is always a peak element. For example, 50 is peak element in {10, 20, 30, 40, 50}.

2. If the input array is sorted in strictly decreasing order, the first element is always a peak element. 100 is the peak element in {100, 80, 60, 50, 20}.

Solution : (Binary Search)

class Solution
{
public:
    int findPeakElement(vector<int> &nums)
    {

        if (nums.size() == 1)
        {
            return 0;
        }

        int start = 0;
        int end = nums.size() - 1;
        int res = -1;
        while (start <= end)
        {

            int mid = (start + end) / 2;

            if (mid > 0 && mid < nums.size() - 1)
            {

                if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1])
                {
                    res = mid;
                    break;
                }
                else if (nums[mid] < nums[mid + 1])
                {
                    start = mid + 1;
                }
                else
                {
                    end = mid - 1;
                }
            }
            
            else if (mid == 0)
            {
                if (nums[mid] > nums[mid + 1])
                {
                    res = mid;
                    break;
                }
                else
                {
                    start = mid + 1;
                }
            }

            else if (mid == nums.size() - 1)
            {
                if (nums[mid] > nums[mid - 1])
                {
                    res = mid;
                    break;
                }
                else
                {
                    end = mid - 1;
                }
            }
        }

        return res;
    }
};

Time Complexity: O(log (n))