Queries for counts of array elements with values in given range | function to find first index >= x ; function to find last index <= y ; function to count elements within given range ; initialize result ; Driver Code ; Preprocess array ; Answer queries
< ? php function lowerIndex ( $ arr , $ n , $ x ) { $ l = 0 ; $ h = $ n - 1 ; while ( $ l <= $ h ) { $ mid = ( $ l + $ h ) / 2 ; if ( $ arr [ $ mid ] >= $ x ) $ h = $ mid - 1 ; else $ l = $ mid + 1 ; } return $ l ; } 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 ; } function countInRange ( $ arr , $ n , $ x , $ y ) { $ count = 0 ; $ count = ( upperIndex ( $ arr , $ n , $ y ) - lowerIndex ( $ arr , $ n , $ x ) + 1 ) ; $ t = floor ( $ count ) ; return $ t ; } $ arr = array ( 1 , 4 , 4 , 9 , 10 , 3 ) ; $ n = sizeof ( $ arr ) ; sort ( $ arr ) ; $ i = 1 ; $ j = 4 ; echo countInRange ( $ arr , $ n , $ i , $ j ) , " " ; $ i = 9 ; $ j = 12 ; echo countInRange ( $ arr , $ n , $ i , $ j ) , " " ; ? >