Queries for counts of array elements with values in given range | function to find first index >= x ; function to find last index <= x ; function to count elements within given range ; initialize result ; driver function ; Preprocess array ; Answer queries
def lowerIndex ( arr , n , x ) : NEW_LINE INDENT l = 0 NEW_LINE h = n - 1 NEW_LINE while ( l <= h ) : NEW_LINE INDENT mid = int ( ( l + h ) / 2 ) NEW_LINE if ( arr [ mid ] >= x ) : NEW_LINE h = mid - 1 NEW_LINE else : NEW_LINE l = mid + 1 NEW_LINE DEDENT return l NEW_LINE DEDENT def upperIndex ( arr , n , x ) : NEW_LINE INDENT l = 0 NEW_LINE h = n - 1 NEW_LINE while ( l <= h ) : NEW_LINE INDENT mid = int ( ( l + h ) / 2 ) NEW_LINE if ( arr [ mid ] <= x ) : NEW_LINE l = mid + 1 NEW_LINE else : NEW_LINE h = mid - 1 NEW_LINE DEDENT return h NEW_LINE DEDENT def countInRange ( arr , n , x , y ) : NEW_LINE INDENT count = 0 ; NEW_LINE count = upperIndex ( arr , n , y ) - lowerIndex ( arr , n , x ) + 1 ; NEW_LINE return count NEW_LINE DEDENT arr = [ 1 , 3 , 4 , 9 , 10 , 3 ] NEW_LINE n = len ( arr ) NEW_LINE arr . sort ( ) NEW_LINE i = 1 NEW_LINE j = 4 NEW_LINE print ( countInRange ( arr , n , i , j ) ) NEW_LINE i = 9 NEW_LINE j = 12 NEW_LINE print ( countInRange ( arr , n , i , j ) ) NEW_LINE