Binary search insertion points: what bisect, lower_bound and binarySearch return

Binary search is taught as a way to find a value, but code often needs a slightly different answer: where would this value go? Python, C++ and Java all provide binary-search APIs, but their return values do not mean the same thing.

Use this array as an example:

a = [1, 2, 4, 5, 5, 6]

An insertion point is a boundary

An insertion point names a gap between elements, not an element. An array of six elements has seven gaps, numbered 0 through 6.

There are two useful boundaries for the value 5:

• less than 5 | 5 or more → 3
• 5 or less | more than 5 → 5

The first is before the first 5. The second is after the last 5. When a value is absent, the two boundaries coincide. For 3, both boundaries are at index 2.

Python: bisect_left and bisect_right

Python’s documentation defines these two boundaries directly.

import bisect

a = [1, 2, 4, 5, 5, 6]
bisect.bisect_left(a, 5)   # 3
bisect.bisect_right(a, 5)  # 5
bisect.bisect_left(a, 3)   # 2

These results were run with Python 3.14.7.

The functions call __lt__, not __eq__, so their return values do not tell you whether the value is present. To check for a match, test that the result of bisect_left is within the sequence and that the element at that position equals the value.

The key argument was added in Python 3.10. For bisect_left and bisect_right, it applies to the sequence elements but not to x.

The sequence is assumed to be sorted. The documentation also says the bisect functions are not thread-safe. Concurrent use on the same sequence, or mutation by another thread during a search, can produce undefined results.

C++: lower_bound and upper_bound

C++ lower_bound returns the same boundary as bisect_left. upper_bound matches bisect_right.

std::vector<int> a{1, 2, 4, 5, 5, 6};

std::lower_bound(a.begin(), a.end(), 5) - a.begin();  // 3
std::upper_bound(a.begin(), a.end(), 5) - a.begin();  // 5

These results were run with Apple clang 17 and -std=c++17.

The C++ requirement is not that the whole range be sorted. The range must be partitioned for the comparison: every element satisfying e < value must appear before every element that does not. An unsorted range can meet that condition for a particular search value. cppreference describes violating the condition as undefined behavior.

Java: Arrays.binarySearch

Java returns an index when it finds the key. When it does not, it returns:

-(insertion point) - 1

The insertion point is the index of the first element greater than the key, or the array length if there is no such element. For 3, the insertion point in the example is 2, so the documented return value is -3. Given a negative result r, -(r + 1) recovers the insertion point.

Duplicates are the catch. The Javadoc says there is no guarantee which matching element will be found. Searching for 5 may return 3 or 4. Arrays.binarySearch is not a lower bound. If you need the first matching position, use a boundary search written for that purpose.

The Java array must be sorted before the call. Otherwise, the result is undefined.

Return values compared

API	Key present	Key absent	Duplicates	Input condition
Python bisect_left	first position	insertion point	before the leftmost	sorted
Python bisect_right	one past the last	insertion point	after the rightmost	sorted
C++ lower_bound	first position	insertion point	before the leftmost	partitioned for the comparison
C++ upper_bound	one past the last	insertion point	after the rightmost	partitioned for the comparison
Java binarySearch	a matching index	-(insertion point) - 1	unspecified match	sorted

None of these APIs checks its ordering precondition for you. Python and Java require sorted input. C++ requires a range partitioned for the comparison used by the search.

For a separate question about what sorting preserves, see stable sort.