Count the number of occurrences in a sorted array [reviewed]

Problem

Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[].
Expected time complexity is $O(Log N)$
For example, given array, {8,8,8,9,9,11,15,16,16,16}, the occurrence of 8 should be 3.



This is the similar question as "Counting the number of occurrence of numbers in the array".

Only difference is that we need to find the occurrence of the specified number instead of all number.
This problem can definitely solved in $O ( \log {N})$ using the binary search.
We need to perform the two binary search operations:

  1) one to find the starting position of the given number in the series 

  2) the other to find the ending position of the given number in the series.

Each runs in $O ( \log {N})$, the occurrence of the given number is equals to $$end - start + 1$$

Here is the complete code running in $O ( \log {N})$.


UPDATE(2019-07-26): Solved the problem again. This time instead of finding the first and last positions of target number via binary search. I just count the occurrence and perform the binary search on both halves  when the target is first found.

Eventually, this new approach does the same number of binary search as previous code but simpler to implement.

Here is an algorithm

Step 1: Use binary search to find the value, t. O(log N)
         - if not found, search either left (arr[half] > target) or right half (arr[half] > target) depending one whether arr[half] and target

Step 2: once found, increase the counter by 1, and binary search for both half.
    - if found, increase the counter and repeat.

Here is a solution in python

Practice statistics

6:00: come up with algorithm.
8:00: to write the code and fix one typo (after running T.T)