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
def binarySearch ( arr , l , r , x ) : NEW_LINE INDENT if ( r < l ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT mid = int ( l + ( r - l ) / 2 ) NEW_LINE if arr [ mid ] == x : NEW_LINE INDENT return mid NEW_LINE DEDENT if arr [ mid ] > x : NEW_LINE INDENT return binarySearch ( arr , l , mid - 1 , x ) NEW_LINE DEDENT return binarySearch ( arr , mid + 1 , r , x ) NEW_LINE DEDENT def countOccurrences ( arr , n , x ) : NEW_LINE INDENT ind = binarySearch ( arr , 0 , n - 1 , x ) NEW_LINE if ind == - 1 : NEW_LINE INDENT return 0 NEW_LINE DEDENT count = 1 NEW_LINE left = ind - 1 NEW_LINE while ( left >= 0 and arr [ left ] == x ) : NEW_LINE INDENT count += 1 NEW_LINE left -= 1 NEW_LINE DEDENT right = ind + 1 ; NEW_LINE while ( right < n and arr [ right ] == x ) : NEW_LINE INDENT count += 1 NEW_LINE right += 1 NEW_LINE DEDENT return count NEW_LINE DEDENT arr = [ 1 , 2 , 2 , 2 , 2 , 3 , 4 , 7 , 8 , 8 ] NEW_LINE n = len ( arr ) NEW_LINE x = 2 NEW_LINE print ( countOccurrences ( arr , n , x ) ) NEW_LINE