CODEWITHSUNDEEP
pythonalgorithmbinary-search
srm26
srm26

Reputation: 11

When are bisect_left(arr, x) and bisect_right(arr, x-1) equal?

If you are doing this on a sorted array arr then would bisect_left(arr, x) == bisect_right(arr, x-1) under any circumstances?

Upvotes: 1

Views: 52

Answers (1)

greybeard
greybeard

Reputation: 2516

From the docs, decorations in square brackets:

The returned insertion point ip partitions the array a into two slices such that
[_left: ] all(elem <  x for elem in a[lo : ip])
[_right:] all(elem <= x for elem in a[lo : ip]) is true for the left slice and
[_left: ] all(elem >= x for elem in a[ip : hi])
[_right:] all(elem >  x for elem in a[ip : hi]) is true for the right slice.

this makes no difference when x is not in a.

But you ask about bisect_left(arr, x) == bisect_right(arr, x-1):
this is True - unless arr contains x-1 < element < x.
Restricted to integers, there is no such value.

Upvotes: 2

Related Questions