Is there a generic binary search routine in a standard library which
a) works for character vectors
b) runs in O(log(N)) time?
I'm aware of findInterval(x,vec), but it is restricted to numeric vectors.
I'm also aware of various hashing solutions (e.g. new.env(hash=TRUE) and
fastmatch), but I need the greatest-lower-bound match in my application.
findInterval is also slow for large N=length(vec) because of the O(N)
checking it does, as Duncan Murdoch has pointed
out<https://stat.ethz.ch/pipermail/r-help/2008-September/174584.html>:
though
its documentation says it runs in O(n * log(N)), it actually runs in O(n *
log(N) + N), which is quite noticeable for largish N. But that is easy
enough to work around by writing a variant of findInterval which calls
find_interv_vec without checking.
-s
PS Yes, binary search is a one-liner in R, but I always prefer to use
standard, fast native libraries when possible....
binarysearch <- function(val,tab,L,H) {while (H>=L) { M=L+(H-L) %/% 2; if
(tab[M]>val) H<-M-1 else if (tab[M]<val) L<-M+1 else return(M)};
return(L-1)}
[[alternative HTML version deleted]]