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
< ? php function LowerInsertionPoint ( $ arr , $ n , $ X ) { if ( $ X < $ arr [ 0 ] ) return 0 ; else if ( $ X > $ arr [ $ n - 1 ] ) return $ n ; $ lowerPnt = 0 ; $ i = 1 ; while ( $ i < $ n && $ arr [ $ i ] < $ X ) { $ lowerPnt = $ i ; $ i = $ i * 2 ; } while ( $ lowerPnt < $ n && $ arr [ $ lowerPnt ] < $ X ) $ lowerPnt ++ ; return $ lowerPnt ; } $ arr = array ( 2 , 3 , 4 , 4 , 5 , 6 , 7 , 9 ) ; $ n = sizeof ( $ arr ) ; $ X = 4 ; echo LowerInsertionPoint ( $ arr , $ n , $ X ) ; ? >