Lower Insertion Point | Function to return the lower insertion point of an element in a sorted array ; Base cases ; Final check for the remaining elements which are < X ; Driver code
def LowerInsertionPoint ( arr , n , X ) : NEW_LINE INDENT if ( X < arr [ 0 ] ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT elif ( X > arr [ n - 1 ] ) : NEW_LINE INDENT return n NEW_LINE DEDENT lowerPnt = 0 NEW_LINE i = 1 NEW_LINE while ( i < n and arr [ i ] < X ) : NEW_LINE INDENT lowerPnt = i NEW_LINE i = i * 2 NEW_LINE DEDENT while ( lowerPnt < n and arr [ lowerPnt ] < X ) : NEW_LINE INDENT lowerPnt += 1 NEW_LINE DEDENT return lowerPnt NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 3 , 4 , 4 , 5 , 6 , 7 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE X = 4 NEW_LINE print ( LowerInsertionPoint ( arr , n , X ) ) NEW_LINE DEDENT