{"id":1511,"date":"2020-07-01T09:32:18","date_gmt":"2020-07-01T09:32:18","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1511"},"modified":"2022-03-28T23:22:36","modified_gmt":"2022-03-28T23:22:36","slug":"find-mountain-top","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/find-mountain-top\/","title":{"rendered":"Find Mountain Top"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Binary Search<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given an array A<\/code> of N<\/code> integers, such that till a point these integers are strictly increasing and after that strictly decreasing, find the element present at that point.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/h4>\n
Input : A = [10, 12, 14, 15, 8, 7, 6]\n\nOutput : 15\n\nExplanation : 15 is the top point. As before 15 all elements are strictly increasing and after 15 all elements are strictly decreasing.<\/code><\/pre>\n
Can we use Binary Search<\/code> here ?<\/em><\/strong>  <\/p>\n
\n
Given that half of the array is sorted in increasing order and the other half in decreasing order and we need to find an element that is greater than both elements, one on the left and one on the right. So Binary Search<\/code> could be an efficient alternative to quickly search for that element in Logarithmic Time Complexity<\/code>.<\/p>\n<\/blockquote>\n
OBSERVATION<\/strong>:   <\/p>\n
\n
The desired element would be the Maximum<\/code> element of the array.<\/p>\n<\/blockquote>\n
SOLVING APPROACH:<\/h3>\n
\n
    \n
  1. \n
    The idea is to use Binary Search<\/code>.  <\/p>\n<\/li>\n
  2. \n
    Initialize start<\/code> and end<\/code> as starting and ending indexes of the array.<\/p>\n<\/li>\n
  3. \n
    Calculate, mid = start + (end - start) \/ 2<\/code>.<\/p>\n<\/li>\n
  4. \n
    For every such mid<\/code> calculated check if the element at mid<\/code> is greater than both of its left and right element. If Yes<\/code> return this element.<\/p>\n<\/li>\n
  5. \n
    Else if element at mid<\/code> is only greater than left element, then go on searching in the right half.<\/p>\n<\/li>\n
  6. \n
    Else, go on searching in the left half till the element is found.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    ILLUSTRATION:<\/h3>\n
    A = [12, 14, 15, 8, 7, 6, 5]\n\ni = 0\nj = 6\nmid = (0 + 6) \/ 2 = 3\nSince, A[3] < A[2]\nj = mid - 1 = 2\n\ni = 0\nj = 2\nmid = (0 + 2) \/ 2 = 1\nSince, A[1] < A[2]\ni = mid + 1 = 2\n\ni = 2\nj = 2\nmid = (2 + 2) \/ 2 = 2\nSince, A[2] > A[1] and A[2] > A[3]\n\nTherefore, A[2] = 15 is our required top point. <\/code><\/pre>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t