Search for an element in a Mountain Array | 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
def findPeak ( arr ) : NEW_LINE INDENT left = 0 NEW_LINE right = len ( arr ) - 1 NEW_LINE while ( left < right ) : NEW_LINE INDENT mid = left + ( right - left ) // 2 NEW_LINE if ( arr [ mid ] < arr [ ( mid + 1 ) ] ) : NEW_LINE INDENT left = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT right = mid NEW_LINE DEDENT DEDENT return left NEW_LINE DEDENT def BS ( X , left , right , arr ) : NEW_LINE INDENT while ( left <= right ) : NEW_LINE INDENT mid = left + ( right - left ) // 2 NEW_LINE if ( arr [ mid ] == X ) : NEW_LINE INDENT return mid NEW_LINE DEDENT elif ( X > arr [ mid ] ) : NEW_LINE INDENT left = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT right = mid - 1 NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT def reverseBS ( X , left , right , arr ) : NEW_LINE INDENT while ( left <= right ) : NEW_LINE INDENT mid = left + ( right - left ) // 2 NEW_LINE if ( arr [ mid ] == X ) : NEW_LINE INDENT return mid NEW_LINE DEDENT elif ( X > arr [ mid ] ) : NEW_LINE INDENT right = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT left = mid + 1 NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT def findInMA ( X , mountainArr ) : NEW_LINE INDENT peakIndex = findPeak ( mountainArr ) NEW_LINE res = - 1 NEW_LINE if ( X >= mountainArr [ 0 ] and X <= mountainArr [ peakIndex ] ) : NEW_LINE INDENT res = BS ( X , 0 , peakIndex , mountainArr ) NEW_LINE DEDENT if ( res == - 1 ) : NEW_LINE INDENT res = reverseBS ( X , peakIndex + 1 , mountainArr . size ( ) - 1 , mountainArr ) NEW_LINE DEDENT print ( res ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT X = 3 NEW_LINE arr = [ 1 , 2 , 3 , 4 , 5 , 3 , 1 ] NEW_LINE findInMA ( X , arr ) NEW_LINE DEDENT