Base cases
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 ; }