Algorithms - Use Binary Search to find first/last occurrence, element count

BINARY SEARCH ON SORTED ARRAYS (FIRST/LAST OCCURRENCE).

GET ELEMENT COUNT IN A SORTED ARRAY.

Taken from  - https://www.youtube.com/watch?v=OE7wUUpJw6I

and https://www.youtube.com/watch?v=pLT_9jwaPLs&feature=player_embedded

BinarySearch(A,size,x):

                low = 0

                high = size – 1

                while low <= high:

mid = (low + high)/2

if A[mid] == x:

                return mid

elif A[mid] > x:

                high = mid -1

else:

                low = mid + 1

return -1

The above is a plain implementation of binary search that immediately returns ‘mid’ once A[mid] == x. So it does not find the first or last occurrence of an element. We easily modify the the above implementation by adding two lines (in yellow) to return the first/last occurrence.

BinarySearchFirstOccurence(A,size,x):

                low = 0

                high = size – 1

                result = -1

                while low <= high:

mid = (low + high)/2

if A[mid] == x:

                result = mid

                high = mid -1

elif A[mid] > x:

                high = mid -1

else:

                low = mid + 1

return result

Note in the above implementation, even if the element is found, we don’t immediately return. We store it in a ‘result’ variable and continue looking ‘leftwards’.  

In case you want to find the last occurrence of an element, you do the same except you continue looking ‘rightwards’.

To find the count of an element, you do lastIndex – firstIndex + 1.