<div dir="ltr"><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">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.</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">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.</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">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.</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">It got me to thinking that it wouldn't be too hard to make a "general" binary search which can search on anything, so that's what I did. I was thinking that it might be interesting to try adding this into the JDK somehow.</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">This implementation is more or less what I now copy & paste to different projects at the moment:</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">    public static <C, T> int binarySearch(C collection, int start, int end, T key, Comparator<? super T> cmp, IntGetter<C, T> getter) {<br>        int low = start;<br>        int high = end - 1;<br>        while (low <= high) {<br>            int mid = low + high >>> 1;<br>            int res = cmp.compare(getter.get(collection, mid), key);<br>            if (res < 0) {<br>                low = mid + 1;<br>            } else if (res > 0) {<br>                high = mid - 1;<br>            } else {<br>                return mid;<br>            }<br>        }<br>        return -low - 1;<br>    }</div><span class="gmail_signature_prefix"><div><span class="gmail_signature_prefix"><span class="gmail_default">    // (Plus variations for `Comparable` keys and long indices)</span></span></div><div><span class="gmail_signature_prefix"><span class="gmail_default"><br></span></span></div><div><span style="font-family:arial,helvetica,sans-serif">A key problem with this approach is that in the JDK, there is no `ObjIntFunction<T, R>` or `ObjLongFunction<T, R>` which would be necessary to implement the "getter" portion of the algorithm (despite the existence of the analogous `ObjIntConsumer<T>` and `ObjLongConsumer<T>`). So, I also have to copy/paste a `IntGetter<T, R>`/`LongGetter<T, R>` as well, which is annoying.</span><br></div><div><br></div><div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">A slightly less-good approach is for the general `binarySearch` method to accept a `IntFunction<T>`/`LongFunction<T>`, and drop the `C collection` parameter, like this:</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">    public static <T> int binarySearch(int start, int end, T key, Comparator<? super T> cmp, IntFunction<T> getter) { ... }<br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">In this case, we can use the function types that the JDK already provides, but we would very likely have to also create a capturing lambda (e.g. `myList::get` instead of `List::get`). Maybe this isn't that bad of a compromise.</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">It would be possible to replace the existing `binarySearch` implementations with delegating calls to a generalized implementation. For `Collections`, the indexed version uses `List::get` and the iterator version uses a helper lambda to move the iterator and get the result. For arrays, a lambda would be provided which gets the corresponding array element. If the non-capturing variant is used, then (on paper at least) this version should perform similarly to the existing implementations, with less code needed overall. However, if a capturing lambda is required (due to the aforementioned lack of `ObjXFunction`), then this could be slightly worse-performing than the existing implementation due to the construction (and maybe dispatch) overhead of the lambda. Some real-world benchmarks would have to be written with various-sized data sets.</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">It would also be possible to produce primitive variations which operate on int, float, long, and double values, using existing functions if capturing is deemed "OK". It is also possible to produce a variation which uses a `long` for the index, for huge data sets (for example, very large mapped files using `MemorySegment`).</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">Also unclear is: where would it live? `Collections`? Somewhere else?</div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><br></div><div class="gmail_default">Any thoughts/opinions would be appreciated (even if they are along the lines of "it's not worth the effort"). Particularly, any insight would be appreciated as to whether or not this kind of hypothetical enhancement would warrant a JEP (I wouldn't think so, but I'm no expert at such assessments).</div><div class="gmail_default"><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><span style="font-family:Arial,Helvetica,sans-serif">--</span><br></div></div></span><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr">- DML • he/him<br></div></div></div>