http://user.it.uu.se/~arnea/ps/searchproc.pdf describes a simple trick that reduces the number of comparisons in a binary search. The same idea can be used for binary search in an array. The idea is to save an index (not a node as described in the paper). In https://github.com/D-Programming-Language/phobos/blob/master/std/range/package.d#L7833 the routine could do only one evaluation of predFun and then continue searching. Only when the count goes down to zero is the other comparison done.
Commits pushed to master at https://github.com/D-Programming-Language/phobos https://github.com/D-Programming-Language/phobos/commit/dda21ec7d1bee229c3e5af80fa06162735a74cb7 Issue 15385 https://github.com/D-Programming-Language/phobos/commit/4a12bd6e08489fba159d307f1ef9059e18fcd4f2 Merge pull request #3844 from Xinok/issue15385 Fix Issue 15385 - SortedRange.contains() optimize predicate calls
Commits pushed to stable at https://github.com/D-Programming-Language/phobos https://github.com/D-Programming-Language/phobos/commit/dda21ec7d1bee229c3e5af80fa06162735a74cb7 Issue 15385 https://github.com/D-Programming-Language/phobos/commit/4a12bd6e08489fba159d307f1ef9059e18fcd4f2 Merge pull request #3844 from Xinok/issue15385