Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

You may also like...