Search for an element in a Mountain Array | Java program for the above approach ; Function to find the index of the peak element in the array ; Stores left most index in which the peak element can be found ; Stores right most index in which the peak element can be found ; Stores mid of left and right ; If element at mid is less than element at ( mid + 1 ) ; Update left ; Update right ; Function to perform binary search in an a subarray if elements of the subarray are in an ascending order ; Stores mid of left and right ; If X found at mid ; If X is greater than mid ; Update left ; Update right ; Function to perform binary search in an a subarray if elements of the subarray are in an ascending order ; Stores mid of left and right ; If X found at mid ; Update right ; Update left ; Function to find the smallest index of X ; Stores index of peak element in array ; Stores index of X in the array ; If X greater than or equal to first element of array and less than the peak element ; Update res ; If element not found on left side of peak element ; Update res ; Print res ; Driver Code ; Given X ; Given array ; Function Call
import java . io . * ; import java . util . * ; class GFG { public static int findPeak ( ArrayList < Integer > arr ) { int left = 0 ; int right = arr . size ( ) - 1 ; while ( left < right ) { int mid = left + ( right - left ) / 2 ; if ( arr . get ( mid ) < arr . get ( mid + 1 ) ) { left = mid + 1 ; } else { right = mid ; } } return left ; } static int BS ( int X , int left , int right , ArrayList < Integer > arr ) { while ( left <= right ) { int mid = left + ( right - left ) / 2 ; if ( arr . get ( mid ) == X ) { return mid ; } else if ( X > arr . get ( mid ) ) { left = mid + 1 ; } else { right = mid - 1 ; } } return - 1 ; } static int reverseBS ( int X , int left , int right , ArrayList < Integer > arr ) { while ( left <= right ) { int mid = left + ( right - left ) / 2 ; if ( arr . get ( mid ) == X ) { return mid ; } else if ( X > arr . get ( mid ) ) { right = mid - 1 ; } else { left = mid + 1 ; } } return - 1 ; } static void findInMA ( int X , ArrayList < Integer > mountainArr ) { int peakIndex = findPeak ( mountainArr ) ; int res = - 1 ; if ( X >= mountainArr . get ( 0 ) && X <= mountainArr . get ( peakIndex ) ) { res = BS ( X , 0 , peakIndex , mountainArr ) ; } if ( res == - 1 ) { res = reverseBS ( X , peakIndex + 1 , mountainArr . size ( ) - 1 , mountainArr ) ; } System . out . println ( res ) ; } public static void main ( String [ ] args ) { int X = 3 ; ArrayList < Integer > list = new ArrayList < > ( Arrays . asList ( 1 , 2 , 3 , 4 , 5 , 3 , 1 ) ) ; findInMA ( X , list ) ; } }