Modified binary search
while ( $ l <= $ r ) { $ m = intval ( ( $ l + $ r ) / 2 ) ; if ( $ arr [ $ m ] < $ key ) { $ l = $ m + 1 ; $ index = $ m ; } else { $ r = $ m - 1 ; } } return ( $ index + 1 ) ; }