I've made the equality comparison its own parameter, and it's based on the comparison function by default rather than being 'is. That way you can find 3.0 by searching for 3 (even though 3 and 3.0 aren't 'is), and you can pass in other comparators like 'iso instead.
I've put in the 'len-stack local and used the 'car of the later portion rather than the 'last of the earlier portion. That lets me avoid doing linear traversals any more than I have to. I don't know if this helps with the time complexity, 'cause the complexity's still linear in the length of the haystack: Even if the caller calculates 'len-stack in constant time (say, using 'qlen) and passes it explicitly, the uses of 'nthcdr ultimately do about as many cdrs as there are elements in the list.
The 'car-versus-'last change does affect the outcome of the algorithm a little: Mine finds the latest applicable index in the list, whereas yours finds the earliest.
I also used 'int instead of 'round. This is apparently a little bit faster (and should have no effect on the results or algorithmic complexity):
Furthermore, I've specifically chosen 'nthcdr over 'split so as to reduce consing (not just to reduce the uses of 'len). Now the only places I suspect memory will be allocated are the lambdas produced by 'withs (which oughta be something the Racket compiler can strip out), maybe possibly the arithmetic (if you're dealing with ridiculously gargantuan list lengths), and miscellaneous runtime overhead associated with things like function calls and variable lookup.
In fact, we probably do have some argument list consing to worry about: Since 'bsearch has optional arguments, it's compiled using 'ac-complex-fn, which makes it a varargs function as far as Racket's concerned.
Here's a version that implements the loop using a non-varargs function:
(load "lib/util.arc") ; for 'xloop
; same as before
(def <-to-== ((o < <))
(fn (a b)
(~or (< a b) (< b a))))
(def bsearch (stack needle (o < <) (o == <-to-==.<))
(xloop (stack stack offset 0 len-stack len.stack)
(case len-stack
0 nil
1 (when (== car.stack needle) offset)
(withs (len-before (int:/ len-stack 2)
after (nthcdr len-before stack))
(if (< needle car.after)
(next stack offset len-before)
(next after
(+ offset len-before) (- len-stack len-before)))))))
arc> (time:repeat 10000 (bsearch '(0 1 4 9 16) 9))
time: 341 msec.
nil
arc> (time:repeat 10000 (bsearch '(0 1 4 9 16) 8))
time: 330 msec.
nil
That's pretty negligible, but it doesn't seem to be quite within the range of error: I've tried this test a few times to account for things like the JIT warming up, and the $.+ version is consistently slightly better.
So yeah, this algorithm is linear in the length of the list, but it still lets you cut down on the number of times the comparison function is called, which is oftentimes the most important thing.
For binary search with insertion or removal, which is a likely operation if we're maintaining a sorted list at runtime, this algorithm is actually especially ideal. We end up with linear-in-length-times-logarithmic-in-comparisons time (plus an allocation for insertion), which is kinda the same as the time complexity on a dynamic array.
To break through these barriers any further, we'd probably need to adapt the surrounding algorithm so it used a fixed-size data structure (cutting down on allocations) and/or a heap (cutting down on the linear-in-length time factor) and/or a more informative model for the the haystack's distribution (so we could use things like Newton's method for better-than-logarithmic search). But this isn't something the implementor of 'bsearch has control over.
