Generalizing binary search

[David Lloyd]

On Thu, Apr 25, 2024 at 2:09 PM Pavel Rappo <pavel.rappo at oracle.com> wrote:

>
>
> > On 25 Apr 2024, at 19:41, David Lloyd <david.lloyd at redhat.com> wrote:
> >
> > The JDK contains a few collection- and array-oriented implementations of
> binary search. For the most part, they all work the same way: search the
> target "thing" by index using the obvious bisection strategy, returning
> either /index/ or /-index-1/ depending on whether it was found at the end
> of the search.
> >
> > However, if you're doing a binary search on a thing that is not a list
> or an array, you have two choices: try to make the thing you're searching
> on implement List (often infeasible) or write your own binary search.
> >
> > I'm really tired of writing my own binary search. I've probably done it
> 50 times by now, each one using a slightly different access and/or compare
> strategy, and every time is a new chance to typo something or get something
> backwards, leading to irritating debugging sessions and higher dentist
> bills.
>
> Can we safely say that it sets your teeth on edge?
>

You could say that. :)

Have a look at this recently filed issue:
> https://bugs.openjdk.org/browse/JDK-8326330


Oh, nice, I didn't see that come across. It's even more general than my
version: I like that. My only complaint is (once again) that the lambda
must be capturing in order to work with a plain
`IntPredicate`/`LongPredicate`.

-- 
- DML • he/him
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20240425/da217131/attachment-0001.htm>