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:


public class FirstDecreasingBruteForce {
public static void find(int [] a){
for (int i = 1; i <a.length ; i++) {
if(a[i]<a[i1]){
System.out.println("First Element from where elements starts decreasing: " + a[i1]);
return;
}
}
//if you have reached here , means no decreasing
System.out.println("Array does not have a decreasing point, Max element is : "+ a[a.length1]);
}
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:


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