Count number of occurrences ( or frequency ) in a sorted array | 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
function binarySearch ( arr , l , r , x ) { if ( r < l ) return - 1 ; var mid = l + parseInt ( ( 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 ) ; } function countOccurrences ( arr , n , x ) { var ind = binarySearch ( arr , 0 , n - 1 , x ) ; if ( ind == - 1 ) return 0 ; var count = 1 ; var left = ind - 1 ; while ( left >= 0 && arr [ left ] == x ) count ++ , left -- ; var right = ind + 1 ; while ( right < n && arr [ right ] == x ) count ++ , right ++ ; return count ; } var arr = [ 1 , 2 , 2 , 2 , 2 , 3 , 4 , 7 , 8 , 8 ] ; var n = arr . length ; var x = 2 ; document . write ( countOccurrences ( arr , n , x ) ) ;