Queries for counts of array elements with values in given range | Efficient C ++ program to count number of 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 function ; Preprocess array ; Answer queries
import java . io . * ; import java . util . Arrays ; class GFG { static int lowerIndex ( int arr [ ] , int n , int x ) { int l = 0 , h = n - 1 ; while ( l <= h ) { int mid = ( l + h ) / 2 ; if ( arr [ mid ] >= x ) h = mid - 1 ; else l = mid + 1 ; } return l ; } static int upperIndex ( int arr [ ] , int n , int y ) { int l = 0 , h = n - 1 ; while ( l <= h ) { int mid = ( l + h ) / 2 ; if ( arr [ mid ] <= y ) l = mid + 1 ; else h = mid - 1 ; } return h ; } static int countInRange ( int arr [ ] , int n , int x , int y ) { int count = 0 ; count = upperIndex ( arr , n , y ) - lowerIndex ( arr , n , x ) + 1 ; return count ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 4 , 4 , 9 , 10 , 3 } ; int n = arr . length ; Arrays . sort ( arr ) ; int i = 1 , j = 4 ; System . out . println ( countInRange ( arr , n , i , j ) ) ; ; i = 9 ; j = 12 ; System . out . println ( countInRange ( arr , n , i , j ) ) ; } }