Binary Search and finding count in a sorted array

If you had the find an element in a sorted array, the first thing that should pop in your mind is binary search. Now a simple algorithm for binary search is mentioned below:

given a sorted array A and a key to be found in the array
lo = 0
hi = A.length - 1
iterate till: lo <= hi
     mid = lo + (hi - lo)/2 
     //better than mid = (lo + hi)/2, because it avoids possible
     //overflow
     if A[mid] > key
          hi = mid - 1
     else if A[mid] < key
          lo = mid + 1
     else
          return mid
return -1 // not found

C++ code:

Now to find the left most element or the right most element we have to tweak the binary search when the key is found to continue looking left or right.

Let’s look at the pseudo code to find the leftmost occurrence below:

result = -1;
...
...
if A[mid] == key
    result = mid
    hi = mid - 1;
...
...
return result;

Similarly the code for the rightmost occurrence is as below:

result = -1;
...
...
if A[mid] == key
    result = mid
    lo = mid + 1;
...
...
return result;

C++ code:

Now to find the total count all we have to do is find the left most and the right most element and return the difference plus one.

count = right - left + 1

C++ code:

If you enjoyed this problem walk-through check out more of my content. Happy coding !!