Binary Search

Find the indices where many elements x[j] would be inserted into a sorted sequence v to maintain the sorted order: the Julia Base functions applied to each query in parallel. There are no allocating forms, because Base.searchsortedfirst(v, x) treats a vector x as one value.

searchsortedfirst!: index of the first element of v not ordered before x[j] (>= x[j] by default).
searchsortedlast!: index of the last element of v not ordered after x[j] (<= x[j] by default).
Other names: thrust::lower_bound, thrust::upper_bound, std::lower_bound.

Example:

import AcceleratedKernels as AK
using Metal

# Sorted array
v = MtlArray(rand(Float32, 100_000))
AK.sort!(v)

# Elements `x` to place within `v` at indices `ix`
x = MtlArray(rand(Float32, 10_000))
ix = MtlArray{Int}(undef, 10_000)

AK.searchsortedfirst!(ix, v, x)

AcceleratedKernels.searchsortedfirst! — Function

searchsortedfirst!(
    ix::AbstractVector, v::AbstractVector, xs::AbstractVector;
    backend=nothing,
    lt=isless, by=identity, rev::Union{Nothing, Bool}=nothing,
    order::Base.Order.Ordering=Base.Order.Forward,
    block_size::Int=256,
    max_tasks::Int=Threads.nthreads(),
    min_elems::Int=1000,
) -> ix

Batched binary search: for each element xs[i], write searchsortedfirst(v, xs[i]; lt, by, rev, order) into ix[i], the index of the first element of the sorted vector v not ordered before xs[i]. Unlike Base.searchsortedfirst, which would treat xs as a single value, every element of xs is a separate query. ix needs as many elements as xs.

backend is derived from ix, v and xs; the launch keywords are those of foreachindex, except that on the host at least min_elems=1000 queries go to each task.

Examples

import AcceleratedKernels as AK
using CUDA

v = CuArray(sort(rand(Float32, 1_000_000)))
xs = CuArray(rand(Float32, 10_000))
ix = similar(xs, Int)
AK.searchsortedfirst!(ix, v, xs)

source

AcceleratedKernels.searchsortedlast! — Function

searchsortedlast!(
    ix::AbstractVector, v::AbstractVector, xs::AbstractVector;
    backend=nothing,
    lt=isless, by=identity, rev::Union{Nothing, Bool}=nothing,
    order::Base.Order.Ordering=Base.Order.Forward,
    block_size::Int=256,
    max_tasks::Int=Threads.nthreads(),
    min_elems::Int=1000,
) -> ix

Batched binary search: for each element xs[i], write searchsortedlast(v, xs[i]; lt, by, rev, order) into ix[i], the index of the last element of the sorted vector v not ordered after xs[i]. The keywords are those of searchsortedfirst!.

source