text: Get free ebooK with 50 must do coding Question for Product Based Companies solved
  Fill the details & get ebook over email
  Thank You!
  We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
  
  # Find Mountain Top
  
  Last Updated on March 28, 2022 by Ria Pathak
  
  Binary Search
  
  Medium
  
  ### PROBLEM STATEMENT`(`SIMPLIFIED`)`:
  
  Given an array `A` of `N` integers, such that till a point these integers are strictly increasing and after that strictly decreasing, find the element present at that point.
  
  See original problem statement here
  
  #### For Example:
  
  ``````Input : A = [10, 12, 14, 15, 8, 7, 6]
  
  Output : 15
  
  Explanation : 15 is the top point. As before 15 all elements are strictly increasing and after 15 all elements are strictly decreasing.``````
  
  Can we use `Binary Search` here ?
  
  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` could be an efficient alternative to quickly search for that element in `Logarithmic Time Complexity`.
  
  OBSERVATION:
  
  The desired element would be the `Maximum` element of the array.
  
  ### SOLVING APPROACH:
  
  1. The idea is to use `Binary Search`.
  
  2. Initialize `start` and `end` as starting and ending indexes of the array.
  
  3. Calculate, `mid = start + (end - start) / 2`.
  
  4. For every such `mid` calculated check if the element at `mid` is greater than both of its left and right element. If `Yes` return this element.
  
  5. Else if element at `mid` is only greater than left element, then go on searching in the right half.
  
  6. Else, go on searching in the left half till the element is found.
  
  ### ILLUSTRATION:
  
  ``````A = [12, 14, 15, 8, 7, 6, 5]
  
  i = 0
  j = 6
  mid = (0 + 6) / 2 = 3
  Since, A[3] < A[2]
  j = mid - 1 = 2
  
  i = 0
  j = 2
  mid = (0 + 2) / 2 = 1
  Since, A[1] < A[2]
  i = mid + 1 = 2
  
  i = 2
  j = 2
  mid = (2 + 2) / 2 = 2
  Since, A[2] > A[1] and A[2] > A[3]
  
  Therefore, A[2] = 15 is our required top point. ``````
  
  ### SOLUTIONS:
  
  ```
  #include <stdio.h>
  
  /* function for find Mountain Top */
  int MountainTop(int *arr, int start, int end){
  while(start <= end){
  int mid = start + (end - start) / 2;
  
  /*if mid index element is greater than both of
  its adjacent elements, this is our top element*/
  if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
  return arr[mid];
  
  /* if mid indexed element is only greater than left element
  this implies top is in the right half */
  else if(arr[mid] > arr[mid - 1])
  start = mid + 1;
  
  /* if mid indexed element is only greater than right element
  this implies top is in the left half */
  else
  end = mid - 1;
  }
  }
  
  int main()
  {
  int t; scanf("%d", &t);
  while(t--){
  int n; scanf("%d", &n);
  int arr[n];
  for(int i=0; i<n; i++)
  scanf("%d", &arr[i]);
  printf("%d\n", MountainTop(arr, 0, n-1));
  }
  return 0;
  }
  ```
  ```
  #include <bits/stdc++.h>
  using namespace std;
  
  /* function for find Mountain Top */
  int MountainTop(int *arr, int start, int end){
  while(start <= end){
  int mid = start + (end - start) / 2;
  
  /*if mid index element is greater than both of
  its adjacent elements, this is our top element*/
  if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
  return arr[mid];
  
  /* if mid indexed element is only greater than left element
  this implies top is in the right half */
  else if(arr[mid] > arr[mid - 1])
  start = mid + 1;
  
  /* if mid indexed element is only greater than right element
  this implies top is in the left half */
  else
  end = mid - 1;
  }
  }
  
  int main()
  {
  int t; cin>>t;
  while(t--){
  int n; cin>>n;
  int arr[n];
  for(int i=0; i<n; i++)
  cin>>arr[i];
  cout<<MountainTop(arr, 0, n-1)<<"\n";
  }
  return 0;
  }
  ```
  ```
  import java.util.*;
  import java.io.*;
  
  public class Main {
  /* function for find Mountain Top */
  static int MountainTop(int []arr, int start, int end){
  while(start <= end){
  int mid = start + (end - start) / 2;
  
  /*if mid index element is greater than both of
  its adjacent elements, this is our top element*/
  if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
  return arr[mid];
  
  /* if mid indexed element is only greater than left element
  this implies top is in the right half */
  else if(arr[mid] > arr[mid - 1])
  start = mid + 1;
  
  /* if mid indexed element is only greater than right element
  this implies top is in the left half */
  else
  end = mid - 1;
  }
  // if no mountain top is present
  return 0;
  }
  
  public static void main(String args[]) throws IOException {
  
  Scanner sc = new Scanner(System.in);
  int t = sc.nextInt();
  while(t != 0){
  int n = sc.nextInt();
  int arr[] = new int[n];
  for(int i=0; i<n; i++)
  arr[i] = sc.nextInt();
  System.out.println(MountainTop(arr, 0, n-1));
  t--;
  }
  }
  }
  ```
  
  Space Complexity: O(1)
  
  [forminator_quiz id="1528"]
  
  This article tried to discuss Binary Search. Hope this blog helps you understand and solve the problem. To practice more problems on Searching you can check out MYCODE | Competitive Programming.
explanation: The provided text extract is a detailed explanation of a coding problem and its solution. It describes a problem where the goal is to find the "mountain top" in an array, which is the element that is greater than its neighbors. The text includes the problem statement, an example, a discussion on using binary search, a solving approach, and an illustration of the algorithm. It also provides code solutions in C, C++, and Java.
  
  The text does not contain a math question or a question and answer in the traditional sense. It is more of a coding problem and its solution.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: Get free ebooK with 50 must do coding Question for Product Based Companies solved
  Fill the details & get ebook over email
  Thank You!
  We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
  
  # Find Mountain Top
  
  Last Updated on March 28, 2022 by Ria Pathak
  
  Binary Search
  
  Medium
  
  ### PROBLEM STATEMENT`(`SIMPLIFIED`)`:
  
  Given an array `A` of `N` integers, such that till a point these integers are strictly increasing and after that strictly decreasing, find the element present at that point.
  
  See original problem statement here
  
  #### For Example:
  
  ``````Input : A = [10, 12, 14, 15, 8, 7, 6]
  
  Output : 15
  
  Explanation : 15 is the top point. As before 15 all elements are strictly increasing and after 15 all elements are strictly decreasing.``````
  
  Can we use `Binary Search` here ?
  
  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` could be an efficient alternative to quickly search for that element in `Logarithmic Time Complexity`.
  
  OBSERVATION:
  
  The desired element would be the `Maximum` element of the array.
  
  ### SOLVING APPROACH:
  
  1. The idea is to use `Binary Search`.
  
  2. Initialize `start` and `end` as starting and ending indexes of the array.
  
  3. Calculate, `mid = start + (end - start) / 2`.
  
  4. For every such `mid` calculated check if the element at `mid` is greater than both of its left and right element. If `Yes` return this element.
  
  5. Else if element at `mid` is only greater than left element, then go on searching in the right half.
  
  6. Else, go on searching in the left half till the element is found.
  
  ### ILLUSTRATION:
  
  ``````A = [12, 14, 15, 8, 7, 6, 5]
  
  i = 0
  j = 6
  mid = (0 + 6) / 2 = 3
  Since, A[3] < A[2]
  j = mid - 1 = 2
  
  i = 0
  j = 2
  mid = (0 + 2) / 2 = 1
  Since, A[1] < A[2]
  i = mid + 1 = 2
  
  i = 2
  j = 2
  mid = (2 + 2) / 2 = 2
  Since, A[2] > A[1] and A[2] > A[3]
  
  Therefore, A[2] = 15 is our required top point. ``````
  
  ### SOLUTIONS:
  
  ```
  #include <stdio.h>
  
  /* function for find Mountain Top */
  int MountainTop(int *arr, int start, int end){
  while(start <= end){
  int mid = start + (end - start) / 2;
  
  /*if mid index element is greater than both of
  its adjacent elements, this is our top element*/
  if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
  return arr[mid];
  
  /* if mid indexed element is only greater than left element
  this implies top is in the right half */
  else if(arr[mid] > arr[mid - 1])
  start = mid + 1;
  
  /* if mid indexed element is only greater than right element
  this implies top is in the left half */
  else
  end = mid - 1;
  }
  }
  
  int main()
  {
  int t; scanf("%d", &t);
  while(t--){
  int n; scanf("%d", &n);
  int arr[n];
  for(int i=0; i<n; i++)
  scanf("%d", &arr[i]);
  printf("%d\n", MountainTop(arr, 0, n-1));
  }
  return 0;
  }
  ```
  ```
  #include <bits/stdc++.h>
  using namespace std;
  
  /* function for find Mountain Top */
  int MountainTop(int *arr, int start, int end){
  while(start <= end){
  int mid = start + (end - start) / 2;
  
  /*if mid index element is greater than both of
  its adjacent elements, this is our top element*/
  if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
  return arr[mid];
  
  /* if mid indexed element is only greater than left element
  this implies top is in the right half */
  else if(arr[mid] > arr[mid - 1])
  start = mid + 1;
  
  /* if mid indexed element is only greater than right element
  this implies top is in the left half */
  else
  end = mid - 1;
  }
  }
  
  int main()
  {
  int t; cin>>t;
  while(t--){
  int n; cin>>n;
  int arr[n];
  for(int i=0; i<n; i++)
  cin>>arr[i];
  cout<<MountainTop(arr, 0, n-1)<<"\n";
  }
  return 0;
  }
  ```
  ```
  import java.util.*;
  import java.io.*;
  
  public class Main {
  /* function for find Mountain Top */
  static int MountainTop(int []arr, int start, int end){
  while(start <= end){
  int mid = start + (end - start) / 2;
  
  /*if mid index element is greater than both of
  its adjacent elements, this is our top element*/
  if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
  return arr[mid];
  
  /* if mid indexed element is only greater than left element
  this implies top is in the right half */
  else if(arr[mid] > arr[mid - 1])
  start = mid + 1;
  
  /* if mid indexed element is only greater than right element
  this implies top is in the left half */
  else
  end = mid - 1;
  }
  // if no mountain top is present
  return 0;
  }
  
  public static void main(String args[]) throws IOException {
  
  Scanner sc = new Scanner(System.in);
  int t = sc.nextInt();
  while(t != 0){
  int n = sc.nextInt();
  int arr[] = new int[n];
  for(int i=0; i<n; i++)
  arr[i] = sc.nextInt();
  System.out.println(MountainTop(arr, 0, n-1));
  t--;
  }
  }
  }
  ```
  
  Space Complexity: O(1)
  
  [forminator_quiz id="1528"]
  
  This article tried to discuss Binary Search. Hope this blog helps you understand and solve the problem. To practice more problems on Searching you can check out MYCODE | Competitive Programming.
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The provided text extract is a detailed explanation of a coding problem and its solution. It describes a problem where the goal is to find the "mountain top" in an array, which is the element that is greater than its neighbors. The text includes the problem statement, an example, a discussion on using binary search, a solving approach, and an illustration of the algorithm. It also provides code solutions in C, C++, and Java.
  
  The text does not contain a math question or a question and answer in the traditional sense. It is more of a coding problem and its solution.
  
  Label: no-question