**ObjecÂtive**: Given an array of integer which is first increasing then decreasing. Find the element in array from which point it starts decreasing.

OR

Given an array of integer which is first increasing then decreasing. Find the maximum element in that array.

**Similar Problem**: Given an array of integer which is first decreasing then increasing. Find the element in array from which point it starts increasing.

OR

Given an array of integer which is first decreasing then increasing. Find the minimum element in that array.

**Example**:

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: Linear Search:**

- Navigate the array and track the element from where array starts decreasing.
- Handle the edge cases.

Time Complexity: O(n)

**Code**:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class FirstDecreasingBruteForce { | |

public static void find(int [] a){ | |

for (int i = 1; i <a.length ; i++) { | |

if(a[i]<a[i–1]){ | |

System.out.println("First Element from where elements starts decreasing: " + a[i–1]); | |

return; | |

} | |

} | |

//if you have reached here , means no decreasing | |

System.out.println("Array does not have a decreasing point, Max element is : "+ a[a.length–1]); | |

} | |

public static void main(String[] args) { | |

// 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}; | |

int [] a = {1,2,3}; | |

find(a); | |

} | |

} |

**Approach 2: Binary Search**

- Modify the binary search.
- If mid element is greater than both its left and right neighbors then we have found our element.
- If mid element is greater than its left neighbor and less than its right neighbor then array is still increasing. Do a recursive call on the right half of the array (mid+1,end).
- If mid element is less than its left neighbor and greater than its right neighbor then array is now decreasing. Do a recursive call on the left half of the array (start, mid).
- Handle the base cases (see the code).

Time Complexity: O(logn)

**Code**:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class FirstDecreasingBinarySearch { | |

public static int find(int[] arrA, int start, int end) { | |

//base case1: array is null | |

if (arrA == null || arrA.length == 0) | |

return –1; | |

//base case2: if only one element is present | |

if (start == end) | |

return start; | |

//base case3: if only two elements are present, then return which ever is maximum | |

if (end == start + 1 && arrA[start] > arrA[end]) | |

return start; | |

//base case4: if only two elements are present, and first element<second element | |

if (end == start + 1 && arrA[start] < arrA[end]) | |

return end; | |

//modified binary search | |

int mid = start + (end – start) / 2; | |

if (arrA[mid] > arrA[mid + 1] && arrA[mid] > arrA[mid – 1]) | |

return mid; | |

else if (arrA[mid] > arrA[mid + 1] && arrA[mid] < arrA[mid – 1]) { | |

return find(arrA, start, mid); | |

} else //if(arrA[mid]==1){ | |

return find(arrA, mid + 1, end); | |

} | |

public static void main(String[] args) { | |

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

int index = find(arrA, 0, arrA.length – 1); | |

System.out.println("(Binary Search) First Element from where elements starts decreasing: (index: "+index+") : " + arrA[index]); | |

} | |

} |

**Output**:

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