Findfirstsorted

General Usage
1

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?

2

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
3 
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
4

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
5

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

6

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

module BinarySearch
    export binary_search_exclusive, binary_search_exclusive_advanced

    function successor_index(i)
        i + true
    end

    function middle_of_two_indices(i, j)
        s = Base.checked_add(i, j)
        s >> true
    end

    function binary_search_exclusive_advanced(
        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}
        binary_search_exclusive_advanced(
            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