Find the increasing OR decreasing point in an array

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:


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:


Output:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: