# Findfirstsorted

**URL:** <https://discourse.julialang.org/t/findfirstsorted/117313>\
**Category:** General Usage\
**Created:** [July 21, 2024, 7:26pm UTC](https://discourse.julialang.org/t/findfirstsorted/117313 "2024-07-21T19:26:10Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![jar1](https://avatars.discourse-cdn.com/v4/letter/j/c0e974/32.png) [@jar1](https://discourse.julialang.org/u/jar1)\
**Post date:** [July 21, 2024, 7:26pm UTC](https://discourse.julialang.org/t/findfirstsorted/117313/1 "2024-07-21T19:26:10Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![DanielVandH](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielvandh/32/31134_2.png) [@DanielVandH](https://discourse.julialang.org/u/DanielVandH)\
**Post date:** [July 21, 2024, 7:41pm UTC](https://discourse.julialang.org/t/findfirstsorted/117313/2 "2024-07-21T19:41:34Z")

</div>

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

```julia
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.

---

<div class="post-metadata">

**Author:** ![jar1](https://avatars.discourse-cdn.com/v4/letter/j/c0e974/32.png) [@jar1](https://discourse.julialang.org/u/jar1)\
**Post date:** [July 21, 2024, 8:08pm UTC](https://discourse.julialang.org/t/findfirstsorted/117313/3 "2024-07-21T20:08:21Z")

</div>

```julia
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

```

---

<div class="post-metadata">

**Author:** ![aplavin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aplavin/32/222056_2.png) [@aplavin](https://discourse.julialang.org/u/aplavin)\
**Post date:** [July 22, 2024, 12:34am UTC](https://discourse.julialang.org/t/findfirstsorted/117313/4 "2024-07-22T00:34:38Z")

</div>

> [@DanielVandH](#):
>
> `x -> x isa Bool ? x : p(x)`

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.

---

<div class="post-metadata">

**Author:** ![DanielVandH](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielvandh/32/31134_2.png) [@DanielVandH](https://discourse.julialang.org/u/DanielVandH)\
**Post date:** [July 22, 2024, 6:17am UTC](https://discourse.julialang.org/t/findfirstsorted/117313/5 "2024-07-22T06:17:59Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [July 22, 2024, 8:18am UTC](https://discourse.julialang.org/t/findfirstsorted/117313/6 "2024-07-22T08:18:49Z")

</div>

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

```julia
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:

```julia
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.