# Find the increasing OR decreasing point in an array

Objec­tive:  Given an array of inte­ger which is first increas­ing then decreas­ing. Find the ele­ment in array from which point it starts decreas­ing.
OR
Given an array of inte­ger which is first increas­ing then decreas­ing. Find the max­i­mum ele­ment in that array.
Sim­i­lar Prob­lem: Given an array of inte­ger which is first decreas­ing then increas­ing. Find the ele­ment in array from which point it starts increas­ing.
OR
Given an array of inte­ger which is first decreas­ing then increas­ing. Find the min­i­mum ele­ment in that array.
Exam­ple:

```int [] a = {1,2,4,6,11,15,19,20,21,31,41,51,55,46,35,24,18,14,13,12,11,4,2,1};
output: 55

int [] a = {1,2,4};  //no deceasing element, so last element will be answer
output: 4

int [] a = {4,2,1};  //no deceasing element, so last element will be answer
output: 4
```

Approach 1: Lin­ear Search:

• Nav­i­gate the array and track the ele­ment from where array starts decreasing.
• Han­dle the edge cases.

Time Com­plex­ity: O(n)

Code:

Approach 2: Binary Search

• Mod­ify the binary search.
• If mid ele­ment is greater than both its left and right neigh­bors then we have found our element.
• If mid ele­ment is greater than its left neigh­bor and less than its right neigh­bor then array is still increas­ing. Do a recur­sive call on the right half of the array (mid+1,end).
• If mid ele­ment is less than its left neigh­bor and greater than its right neigh­bor then array is now decreas­ing. Do a recur­sive call on the left half of the array (start, mid).
• Han­dle the base cases (see the code).

Time Com­plex­ity: O(logn)

Code:

Out­put:

`(Binary Search) First Element from where elements starts decreasing: (index: 12) : 55`