Binary Search For Duplicate Data

GOAL

The goal of this article it to describe an algorithm to find first target item or last target item from sorted list with duplication using binary search and how to implement them in C++.

What is binary search?

Binary search is one of the search algorithms, that finds position or judges existence of an target value on sorted array.

Binary search compares the current value defined as a half of target range of the array to the target value. Binary search compares the middle element of current target range in the array to the target value. The current target range is narrowed according to the result of comparison as below.

What if there are same values in the array?

If there are same values, the found element can be first one, last one or other. How can we change this algorithm to search for the smallest or largest element?

Find first index

If the value currently focused is equal to the target value, the current value is contained to the next range as a max value. End the process when min index equal to max index, then check if the min value is equal to the target value.