function to find last index <= y
function upperIndex ( $ arr , $ n , $ y ) { $ l = 0 ; $ h = $ n - 1 ; while ( $ l <= $ h ) { $ mid = ( $ l + $ h ) / 2 ; if ( $ arr [ $ mid ] <= $ y ) $ l = $ mid + 1 ; else $ h = $ mid - 1 ; } return $ h ; }