# Findfirstsorted

I’m looking for a predicate version of binary search.

That is, a function that tests a predicate `p(x)` on elements of an array `xs` and finds the first index `i` for which `p(xs[i])` returns `true`, assuming that `i < j implies (p(xs[i]) implies p(xs[j]))`, i.e that `i::Int -> p(xs[i])::Bool` is increasing.

Does this function exist somewhere?

I think you can get kinda close using `searchsortedfirst` using something like

``````searchsortedfirst(xs, true, by = x -> x isa Bool ? x : p(x))
``````

The need for `x isa Bool` is that the `by` function also transforms the second argument to `searchsortedfirst`. If this argument is instead something where `p(x)` is true then it’s not needed I think. Maybe there’s a better way.

1 Like
``````using FlexiMaps

julia> findfirstsorted(f, xs) =
searchsortedfirst(mapview(f, xs), true)

findfirstsorted(10:10:1000) do x
println(x)
x>300
end
510
260
390
330
300
320
310
31
``````
1 Like

Oh, that should only be used for self-contained usecases, quite dangerous for general usage… Like, if `xs::Vector{Bool}`.

The `mapview` solution is the fully correct one, and shouldn’t have a lot of overhead.

1 Like

If xs is a vector of Bools, I don’t see what predicate function (other than `p = !`…) would make sense here since it needs to be monotonic

Here’s something more general, subsuming both `searchsortedfirst` and the problem you pose:

``````module BinarySearch

function successor_index(i)
i + true
end

function middle_of_two_indices(i, j)
s >> true
end

index_pred::IndexPredicate,
i, j,  # inclusive
middle_index::MiddleIndex,
succ_index::SuccessorIndex,
is_less::IsOrderedPredicate,
) where {IndexPredicate,MiddleIndex,SuccessorIndex,IsOrderedPredicate}
if is_less(j, i)
throw(ArgumentError("invalid range"))
end
# after `Search` from Go's `sort` stdlib:
#
# https://github.com/golang/go/blob/3959d54c0bd5c92fe0a5e33fedb0595723efc23b/src/sort/search.go#L58-L73
while is_less(i, j)
h = middle_index(i, j)
if index_pred(h)
j = h
else
i = succ_index(h)
end
end
i
end

"""
binary_search_exclusive(predicate, i, j)

Perform binary search on the range from `i` (inclusive) to `j` (exclusive).
"""
function binary_search_exclusive(p::P, i, j) where {P}
p, i, j, middle_of_two_indices, successor_index, isless,
)
end
end
``````

A test suite:

``````using Test

@testset "binary search" begin
using .BinarySearch
@testset "all false" begin
for i ∈ -5:5
for j ∈ i:5
@test j === binary_search_exclusive(Returns(false), i, j)
end
end
end
@testset "all true" begin
for i ∈ -5:5
for j ∈ i:5
@test i === binary_search_exclusive(Returns(true), i, j)
end
end
end
@testset "all false except last" begin
for i ∈ -5:5
for j ∈ (i + 1):5
function pred(n)
if !(i ≤ n < j)
error("unexpected")
end
if n == j - 1
true
else
false
end
end
@test (j - 1) === binary_search_exclusive(pred, i, j)
end
end
end
@testset "all true except first" begin
for i ∈ -5:5
for j ∈ (i + 1):5
function pred(n)
if !(i ≤ n < j)
error("unexpected")
end
if n == i
false
else
true
end
end
@test (i + 1) === binary_search_exclusive(pred, i, j)
end
end
end
# TODO: test against linear search exhaustively for small cases
end
``````

Probably there should be a package.

The implied collection/indices here ranges from `i` to `j`, where `j` is exclusive (thus the name `binary_search_exclusive`). The “exclusive” part is not usual for Julia, but some thought would be required to adapt the code to the inclusive model.

2 Likes