Classic binary search returns an index when an equivalent item is found, or a special value if no equivalent item is present.
It can be more useful to use forms of binary search that return either he lowest or highest index at which the item could be inserted while still maintaining a sorted array. (Strictly speaking, it is maintaining an array that is partitioned with respect to the new item. That weaker criterion is sufficient, and it is not necessary that the data be fully sorted.)
The best way to achieve this varies by language. This shows some demonstration code in Python, C++, and Java:
-
In C++, these are called
std::lower_boundandstd::upper_bound. (std::equal_rangeis available if you want both.)bounds.cppjust demonstrates the standard library functions; it doesn't reimplement them. -
In Python, they are called
bisect.bisect_leftandbisect.bisect_right. (bisect.bisectis another name forbisect.bisect_right.) But I've reimplemented with the C++ names inbounds.py. -
In Java, the standard library does not offer them. (It offers binary search, but not these forms of it.) But they can be implemented without trouble, as shown in
bounds.java.
Binary Search - A Different Perspective | Python
Algorithms
by mCoding (James
Murphy)