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
< ? php function binarySearch ( & $ arr , $ l , $ r , $ x ) { if ( $ r < $ l ) return -1 ; $ 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 ) ; } function countOccurrences ( $ arr , $ n , $ x ) { $ ind = binarySearch ( $ arr , 0 , $ n - 1 , $ x ) ; if ( $ ind == -1 ) return 0 ; $ count = 1 ; $ left = $ ind - 1 ; while ( $ left >= 0 && $ arr [ $ left ] == $ x ) { $ count ++ ; $ left -- ; } $ right = $ ind + 1 ; while ( $ right < $ n && $ arr [ $ right ] == $ x ) { $ count ++ ; $ right ++ ; } return $ count ; } $ arr = array ( 1 , 2 , 2 , 2 , 2 , 3 , 4 , 7 , 8 , 8 ) ; $ n = sizeof ( $ arr ) ; $ x = 2 ; echo countOccurrences ( $ arr , $ n , $ x ) ; ? >