Interview Questions
Find values in sorted array
Given sorted array of 100000 integer values, write a function that will return number of occurrences of value k in the input array.
View Solution
The simplest approach (the brute force) is to visit all elements in the array from left to right and to increment a counter each time we encounter value k. This is O(n) soluton and sinice it was very simple you should suspect that you can do better that that.
Another approach is to use binary search algorithm, which allows us to find a value with sorted array in O(logn) time. The trick is to look for lower bound the first time around, then for upper bound. The result is the upper-bound index of value k, minus the index at lower-bound. Be careful with off-by-one errors, this algorithm is difficult to get right the first time. If you find yourself fixing off-by one errors take a step back and re-think when algorithm should stop for all cases.
In solution below, index 'i' stops before value 'k' when looking for lower-bound and at last index of 'k', when we look for upper-bound value of 'k'. Note: Your solution should correctly handle the case when 'k' does not exist in the input array.
int BinarySearch(vector<int> &a, int k, bool lowerBound)
{
int count = a.size();
int i = 0;
while (count > 0)
{
int step = count / 2;
if (lowerBound ? (a[i + step] < k) : (a[i + step] <= k))
{
i = i + step + 1;
count -= step + 1;
}
else
{
count = step;
}
}
return i;
}
int CountValueOccurrences(vector<int> &a, int k)
{
int lb = BinarySearch(a, k, true);
int ub = BinarySearch(a, k, false);
return ub - lb;
}