searchsorted2

searchsorted2.jl

function searchsortedfirst2vec(a,b)
	[searchsortedfirst(a,bb, 1, length(a), Base.Sort.Forward) for bb in b]
end
c=searchsorted2(a,b)

# returns an array of indicies into a such that each points is the first value in a[i] greater than b[i]
# assumes both a and b are sorted
function searchsortedfirst2a(a,b,o::Base.Sort.Ordering=Base.Sort.Forward)
	alow = 1
	out = Array(Int, length(b))
	@inbounds for i in 1:length(b)
		x=b[i] # this part is essentially the code from searchsortedfirst, but it didn't inline so it was slower when I just called the function
	    lo = alow-1
	    hi = length(a)+1
	    @inbounds while lo < hi-1
	        m = (lo+hi)>>>1
	        if Base.Sort.lt(o,a[m],x)
	            lo = m
	        else
	            hi = m
	        end
	    end
	    alow = hi
		out[i]=hi
	end
	out
end

# this is the better implmentatino thanks to young
# its O(n+m)
function searchsortedfirst2(a,b)
	ia,ib=1,1
	out = Array(Int, length(b))
	@inbounds while ib <= length(b)
		x=b[ib]
		@inbounds while ia<=length(a) && a[ia]<x 
			ia+=1
		end
		out[ib]=ia
		ib+=1
	end
	out
end



# best case comparison for searchsortedfirst2
a=zeros(10^7);
a[10_000_000]=1;
b=ones(10^7);

@time searchsortedfirst2vec(a,b);
@time searchsortedfirst2a(a,b);
@time searchsortedfirst2(a,b);

assert(searchsortedfirst2a(a,b)==searchsortedfirst2vec(a,b))
assert(searchsortedfirst2(a,b)==searchsortedfirst2vec(a,b))

# evently distributed comparison
a = [1:10^7];
b = [1:2:10^7];

@time searchsortedfirst2vec(a,b);
@time searchsortedfirst2a(a,b);
@time searchsortedfirst2(a,b);

assert(searchsortedfirst2a(a,b)==searchsortedfirst2vec(a,b))
assert(searchsortedfirst2(a,b)==searchsortedfirst2vec(a,b))