Question:

An array arr a mountain if the following properties hold:

arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given a mountain array arr, return the index i _such that _arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

Example 1:

Input: arr = [0,1,0]
Output: 1

Example 2:

Input: arr = [1,2,3,2,1]
Output: 2

Intuition:

Let's start with breaking down the question.
Basically we are given an array which contains two parts inside an array.
One which is in strictly increasing order and after that one which is strictly in decreasing order.
Example: {1,2,3,4,5,4,3,2,1}
Now it's obvious that there will be an element which separates those two sections is 5.
Here we need to find that element's index.
We can look this as two arrays who are sorted, one in increasing order and one in decreasing order.
We can use binary search that is applicable on sorted arrays to find our element.
Refer to algorithm for more understanding.

Algorithm: Binary Search

Initializing variables:

We need two variables start and end which refer to our starting and ending points in a binary search.
MID of an array is nothing but (start + end )/2.

Traversion:

We then traverse the array and find the middle each time our loop runs.
If the element we are currently at is less than the element it's next , it means we are in the left section(strictly increasing section) of our array and need to go ahead. So we jump our start to mid+1.
If it's not greater , it consequently means we are in the right section of our array and need to shift our end back to the mid element.
When we are not able to traverse anymore that's when our start and end have reached an element that satisfies neither of the if conditions.
Hence we return our answer which is the element start is pointing to.

Code:

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int start = 0;
        int end = arr.size() -1;

        while (start < end){
            int mid = start + (end-start)/2;
            if (arr[mid] < arr[mid+1]){
                start = mid +1;
            }
            else{
                end = mid;
            }


        }
        return start;
    }
};

Complexity Analysis:

Time: O(logN)
Space: O(1)

DAY 52 - Peak Index in a Mountain Array