General binary search?

-----Original Message-----
From: r-help-bounces at r-project.org 
[mailto:r-help-bounces at r-project.org] On Behalf Of Stavros Macrakis
Sent: Monday, April 04, 2011 1:15 PM
To: r-help
Subject: [R] General binary search?

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]]