# Peak Index in a Mountain Array  Difficulty Level Easy
Array Binary Search

## What is Peak Index in a Mountain Array Problem?  An array can be said as a Mountain Array if it shows the following properties:

1. The length of the given array is should be greater than or equal to 3 LENGTH >=3.
2. There can be only one peak or largest element in the array.
3. It should follow : ARRAY < ARRAY < ARRAY[i-1] < ARRAY[ i] > ARRAY[ i+1 ] > ARRAY[..] > ARRAY[length-1]

Our task is to find the peak index in mountain array.

## Example  Input

[10, 20, 30, 20, 10]

Output

2

Explanation

Index “2” i.e., “30” has the largest value. Input

[0, 2, 1, 0]

Output

1

Explanation

Index “1” i.e., “2” has the largest value.

## Algorithm  1. Set low to 0.
2. Set high to the length of array minus 1.
3. Declare a variable mid.
4. Set mid = low + ( high – low ) / 2.
5. While low < high:
1. If array[ mid ] > = array [ mid + 1].
1. then high = mid.
2. Else
1. then low = mid + 1.
6. Return low.

## Explanation  So we have to find the peak index in a given array. For this we gonna use a binary search approach a little. We have function declare in our code named as getPeakIndex in which we pass our input array and the length of an array.

K’th Largest element in BST using constant extra space

We declared a mid and initialize to 0 and high is equal to high-1, we are going to open a while loop and it will last until it false the condition of low < high. Entering in a loop we set mid=low+(high-low) / 2.

Example

Our input values are:{4,8,16,32,27,9,3};

So the value of high will be array length -1 => 7 – 1 = 6

High=6

Low=0

mid=low+(high-low) / 2 => 0 + ( 6 – 0) / 2 = 3

mid = 3.

Now it gonna checwok if ( array [ mid ] >= array[ mid+1 ] )

i.e, 32 is greater than or equal to 27 the condition is going to be true and set high = mid

So now low=0,

High=3,

Mid=3;

mid=low+(high-low) / 2 => 0 + ( 3 – 0) / 2 = 1

mid = 1.

Now it gonna check if ( array [ mid ] >= array[ mid+1 ] )

i.e, 8 is greater than or equal to 16 the condition is going to be false and execute else part and set low = mid +1;

So now low=2,

High=3,

Mid=1;

mid=low+(high-low) / 2 => 2 + ( 3 – 2) / 2 = 2

mid = 2.

Now it gonna check if ( array [ mid ] >= array[ mid+1 ] )

i.e, 16 is greater than or equal to 32 the condition is going to be false and execute else part and set low = mid +1;

So now low=3,

High=3,

Mid=3;

And here when it comes in loop while ( low < high ), means 3< 3 and it is false

And comes out of loop and return low i.e, low=3.

And the output will become :

peak index is : 3

## Implementation in C++  ```#include <iostream>
using namespace std;

int peakIndex(int arr[],int high)
{
int low=0;
int mid;
high-=1;
while( low < high )
{
mid = low +(high - low)/2;
if(arr[mid]>=arr[mid+1])
{
high=mid;
}
else
{
low=mid+1;
}
}
return low;
}
int main()
{
int mountainArray[]= {4,8,16,32,27,9,3};
int n = sizeof(mountainArray)/sizeof(mountainArray);
int peak=peakIndex(mountainArray,n);
cout<<"Peak index is:"<<peak;
return 0;
}```
`Peak index is:3`

## Implementation in Java  ```class peakIndex {
public static int getPeakIndex(int[] array) {
int low = 0;
int high = array.length - 1;
int mid;
while (low<high) {
mid = low + (high - low) / 2;
if (array[mid] >= array[mid + 1]) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}

public static void main(String[] args) {
peakIndex pi = new peakIndex();
int mountainArray[] = { 4, 8, 16, 32, 27, 9, 3 };
int peak = getPeakIndex(mountainArray);
System.out.println("Peak index is:" + peak);
}
}```
`Peak index is:3`

## Complexity Analysis  ### Time Complexity

O(log n) where n is the length of the array.