Re: [R] General binary search?

From: Matthew Dowle <>
Date: Tue, 05 Apr 2011 09:42:33 +0100

Try data.table:::sortedmatch, which is implemented in C. It requires it's input to be sorted (and doesn't check)

"Stavros Macrakis" <> wrote in message
> 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<>:
> 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]]
> mailing list PLEASE do read the posting guide and provide commented, minimal, self-contained, reproducible code. Received on Tue 05 Apr 2011 - 08:46:02 GMT

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.2.0, at Tue 05 Apr 2011 - 09:40:27 GMT.

Mailing list information is available at Please read the posting guide before posting to the list.

list of date sections of archive