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})$.

	#include<iostream>
	using namespace std;
	int find_first(int s, int e, int*A, int t, int first)
	{
	int start, end;
	if (s > e)
	return first;
	int h = s + (e-s)/2;
	if (A[h] == t)
	{
	first = h;
	start = s;
	end = h-1;
	} else if (A[h] < t)
	{
	start = h+1;
	end = e;
	} else {
	start = s;
	end = h-1;
	}
	return find_first(start, end, A, t, first);
	}
	int find_last(int s, int e, int*A, int t, int last)
	{
	int start, end;
	if (s > e)
	return last;
	int h = s + (e-s)/2;
	if (A[h] == t)
	{
	last = h;
	start = h+1;
	end = e;
	} else if (A[h] < t)
	{
	start = h+1;
	end = e;
	} else {
	start = s;
	end = h-1;
	}
	return find_last(start, end, A, t, last);
	}
	int count_occurrence(int s, int e, int* A, int t)
	{
	if (s > e)
	return -1;
	int start = find_first(s, e, A, t, -1);
	if (start == -1)
	return start;
	int end = find_last(s, e, A, t, -1);
	if (end == -1)
	return end;
	return end - start +1;
	}
	int main()
	{
	int input[11] = {8,8,8,9,9,10,11,15,16,16,16};
	cout <<" 8 is appear "<< count_occurrence(0, 10, input, 8)<<endl;
	cout <<" 9 is appear "<< count_occurrence(0, 10, input, 9)<<endl;
	cout <<" 15 is appear "<< count_occurrence(0, 10, input, 15)<<endl;
	return 1;
	}

view raw count_occurrence_of_number.cpp hosted with ❤ by GitHub

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

	class CountingBinarySearch:
	def search(self, list, target):
	self.count = 0
	self.binary_search(list, target, 0, len(list) - 1)
	return self.count
	def binary_search(self, list, target, s, e):
	if s > e:
	return
	half = s + (e-s)//2
	if list[half] == target:
	self.count +=1
	#search both side
	self.binary_search(list, target, s, half - 1)
	self.binary_search(list, target, half + 1, e)
	elif list[half] < target:
	#search right side
	self.binary_search(list, target, half + 1, e)
	else:
	#search left side
	self.binary_search(list, target, s, half - 1)
	c = CountingBinarySearch()
	input = [8,8,8,9,9,11,15,16,16,16]
	target = 8
	print ("input = {} target = {} output = {}".format(input, target, c.search(input, target)))

view raw count_occurrence_integer_in_sorted_array.py hosted with ❤ by GitHub

Practice statistics

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