Count number of occurrences ( or frequency ) in a sorted array | C # program to count occurrences of an element ; A recursive binary search function . It returns location of x in given array arr [ l . . r ] is present , otherwise - 1 ; If the element is present at the middle itself ; If element is smaller than mid , then it can only be present in left subarray ; Else the element can only be present in right subarray ; Returns number of times x occurs in arr [ 0. . n - 1 ] ; If element is not present ; Count elements on left side . ; Count elements on right side . ; Driver code
using System ; class GFG { static int binarySearch ( int [ ] arr , int l , int r , int x ) { if ( r < l ) return - 1 ; int mid = l + ( r - l ) / 2 ; if ( arr [ mid ] == x ) return mid ; if ( arr [ mid ] > x ) return binarySearch ( arr , l , mid - 1 , x ) ; return binarySearch ( arr , mid + 1 , r , x ) ; } static int countOccurrences ( int [ ] arr , int n , int x ) { int ind = binarySearch ( arr , 0 , n - 1 , x ) ; if ( ind == - 1 ) return 0 ; int count = 1 ; int left = ind - 1 ; while ( left >= 0 && arr [ left ] == x ) { count ++ ; left -- ; } int right = ind + 1 ; while ( right < n && arr [ right ] == x ) { count ++ ; right ++ ; } return count ; } public static void Main ( ) { int [ ] arr = { 1 , 2 , 2 , 2 , 2 , 3 , 4 , 7 , 8 , 8 } ; int n = arr . Length ; int x = 2 ; Console . Write ( countOccurrences ( arr , n , x ) ) ; } }