# Built-in binary search for sorted collections

**URL:** <https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374>\
**Category:** General Usage\
**Tags:** sorting\
**Created:** [April 24, 2025, 2:13pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374 "2025-04-24T14:13:43Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [April 24, 2025, 2:13pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/1 "2025-04-24T14:13:43Z")

</div>

Given integers `N` and `k`, I’d like to elegantly find the largest integer n for which `binomial(n,k) <= N`. A way to do this is

```julia
function max_n_binom_leq(N::Integer, k::Integer) 
    return maximum(n for n=k:N if binomial(big(n),k) ≤ N) 
end

```

This is wasteful. because it has complexity O(N) instead of O(log N). The function `n -> binomial(big(n),k)` is strictly increasing. A better way is to do bisection (binary search). But I wish to avoid implementing it on my own. Does Julia have some built-in methods to solve this elegantly? I would especially like to avoid allocating the whole array `k:N`, since `N` might be very large, like `typemax(UInt128)`.

---

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [April 24, 2025, 2:33pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/2 "2025-04-24T14:33:48Z")

</div>

[searchsortedlast](https://docs.julialang.org/en/v1/base/sort/#Base.Sort.searchsortedlast)

Something like `searchsortedlast(k:N,N,by=n->binomial(big(n),k)) + (k-1)`

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [April 24, 2025, 3:18pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/3 "2025-04-24T15:18:45Z")

</div>

You don’t really have to search much to find this. Even with a very crude approximation like

```julia
binomial(n, k) = n * (n - 1) * ... * (n - (k - 1)) / k! ≈ (n - (k - 1) / 2)^k / k!

```

you can solve for `n` in closed form and end up somewhere close. With better approximations you can probably get spot on.

---

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [April 26, 2025, 3:50pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/4 "2025-04-26T15:50:05Z")

</div>

@Jeff_Emanuel Your suggestion gives an incorrect answer:

```julia
julia> N, k = typemax(UInt16), 10
julia> max_n_binom_leq(N,k)
18
julia> searchsortedlast(k:N,N,by=n->binomial(big(n),k)) + (k-1)
65535

```

@GunnarFarneback Maybe in my particular case, an approximation solves the problem, but not in general. I’ve decided to write my own function:

```julia
function sortedfindfirst(x::AbstractVector{te}, f::F) ::te where {te, F<:Function}
    a = BigInt(1)
    c = BigInt(hasmethod(step,(typeof(x),)) ? floor((big(last(x)) - big(first(x))) / big(step(x))) + 1 : length(x)) # Range vs Vector
    @assert c≥1
    @assert isa(f(x[c]), Bool) && f(x[c])
    while a+1 < c # bisection loop
        b = a+(c-a)÷2 # equivalent to (a+c)÷2 but does not overflow
        (a,c) = !f(x[a]) && f(x[b]) ? (a,b) : (b,c)
    end
    return f(x[a]) ? x[a] : x[c] 
end

```

For example, to numerically solve the transcendental equation x=log(x)^2, we’d just use:

```julia
julia> @time sortedfindfirst(0:1e-10:1, x -> x>log(x)^2)
  0.027249 seconds (28.80 k allocations: 1.460 MiB, 99.59% compilation time)
0.4948664146

```

---

<div class="post-metadata">

**Author:** ![abraemer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraemer/32/51403_2.png) [@abraemer](https://discourse.julialang.org/u/abraemer)\
**Post date:** [April 26, 2025, 7:47pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/5 "2025-04-26T19:47:39Z")

</div>

> [@Leo\_I](#):
>
> ```julia
> function sortedfindfirst(x::AbstractVector{te}, f::F) ::te where {te, F<:Function}
> a = BigInt(1)
> c = BigInt(hasmethod(step,(typeof(x),)) ? floor((big(last(x)) - big(first(x))) / big(step(x))) + 1 : length(x)) # Range vs Vector
> @assert c≥1
> @assert isa(f(x[c]), Bool) && f(x[c])
> while a+1 < c # bisection loop
> b = (a+c)÷2
> (a,c) = !f(x[a]) && f(x[b]) ? (a,b) : (b,c)
> end
> return f(x[a]) ? x[a] : x[c] 
> end
> 
> ```

That seems a bit more convoluted than necessary. You can index ranges just like a Vector and using BigInt as indices should not be necessary.  
So I think you could just write:

```julia
function sortedfindfirst(f::F, x::AbstractVector{te}) ::te where {te, F<:Function}
    a = firstindex(x)
    c = lastindex(x)
    @assert c≥1
    @assert isa(f(x[c]), Bool) && f(x[c])
    while a+1 < c # bisection loop
        b = (a+c)÷2
        (a,c) = !f(x[a]) && f(x[b]) ? (a,b) : (b,c)
    end
    return f(x[a]) ? x[a] : x[c] 
end

```

I also put the function argument first as is convention in Julia.  
(I am on mobile and did not run this code)

---

<div class="post-metadata">

**Author:** ![bertschi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bertschi/32/33462_2.png) [@bertschi](https://discourse.julialang.org/u/bertschi)\
**Post date:** [April 26, 2025, 9:18pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/6 "2025-04-26T21:18:27Z")

</div>

The problem with searchsortedlast is documented here:

```julia-repl
help?> searchsortedlast
...
 Note that the by function is applied to the searched value x as well as the values in v.

```

It can be made to work though, by applying the function to the values only, i.e.,

```julia
let f(n) = binomial(big(n),k); (k:N)[searchsortedlast(f.(k:N), N)] end

```

which unnecessarily evaluates `binomal` for all input values though. Yet, we can delay evaluation and use the by argument to force the values needed:

```julia
macro delay(expr) :(() -> $(esc(expr))) end
force(x) = x()
let f(n) = @delay binomial(big(n),k); (k:N)[searchsortedlast(f.(k:N), @delay N; by = force)] end

```

---

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [April 27, 2025, 10:00am UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/7 "2025-04-27T10:00:48Z")

</div>

> That seems a bit more convoluted than necessary. You can index ranges just like a Vector and using BigInt as indices should not be necessary.

I would prefer to avoid a convoluted solution, yes, but there are problems:

```julia
julia> N=typemax(UInt64); x = 0:N; typeof(lastindex(x)), lastindex(x), length(x)
(UInt64, 0x0000000000000000, 0x0000000000000000)

```

@abraemer Any advice on how to handle those cases?

@bertschi Thanks, but that sounds way too complicated for just a mere bisection use.

---

<div class="post-metadata">

**Author:** ![abraemer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraemer/32/51403_2.png) [@abraemer](https://discourse.julialang.org/u/abraemer)\
**Post date:** [April 27, 2025, 11:06am UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/8 "2025-04-27T11:06:14Z")

</div>

> [@Leo\_I](#):
>
> I would prefer to avoid a convoluted solution, yes, but there are problems:

Oof, nice edge case 😅  
Will searching all values of a number type be a common case for you?  
Anyhow for this I case I would create another method:

```julia
function sortedfindfirst(f::F, ::T) ::te where {T::Type{<:Integer}, F<:Function}
    a = typemin(T)
    c = typemax(T)
    I = oneunit(T)
    I2 = I+I
    @assert isa(f(c), Bool) && f(c)
    while a+I < c # bisection loop
        b = (a+c)÷I2
        (a,c) = !f(a) && f(b) ? (a,b) : (b,c)
    end
    return f(a) ? a : c
end

```

Again untested because I am on mobile.  
For Floats you’d need a slightly different code.

---

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [April 27, 2025, 11:15am UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/9 "2025-04-27T11:15:46Z")

</div>

Hmm, doubling the amount of code just for this case is ugly to me. Besides, it seems somehow wrong to me that `lastindex` and `length`of `0:typemax(UInt))` is `0` even though iterating through this range is nonempty. Could this be considered a bug in Base Julia?

The casting seems inconsistent to me:

```julia
julia> for te∈(Int8,UInt8,Int16,UInt16,Int32,UInt32,Int64,UInt64,Int128,UInt128)  
       x = typemin(te):typemax(te); idx=lastindex(x); len=length(x); println(typeof(idx)," ",typeof(len)," ",big(idx)," ",big(len)) end
Int64 Int64 256 256
Int64 Int64 256 256
Int64 Int64 65536 65536
Int64 Int64 65536 65536
Int64 Int64 4294967296 4294967296
Int64 Int64 4294967296 4294967296
Int64 Int64 0 0
UInt64 UInt64 0 0
Int128 Int128 0 0
UInt128 UInt128 0 0

```

---

<div class="post-metadata">

**Author:** ![bertschi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bertschi/32/33462_2.png) [@bertschi](https://discourse.julialang.org/u/bertschi)\
**Post date:** [April 27, 2025, 12:26pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/10 "2025-04-27T12:26:49Z")

</div>

> [@Leo\_I](#):
>
> Besides, it seems somehow wrong to me that `lastindex` and `length`of `0:typemax(UInt))` is `0` even though iterating through this range is nonempty. Could this be considered a bug in Base Julia?

That certainly sounds like a bug … seems like the line `a += stop - start # Signed are allowed to go negative` in the `length(::AbstractUnitRange)` method overflows in this case.

---

<div class="post-metadata">

**Author:** ![bertschi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bertschi/32/33462_2.png) [@bertschi](https://discourse.julialang.org/u/bertschi)\
**Post date:** [April 27, 2025, 12:30pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/11 "2025-04-27T12:30:21Z")

</div>

> [@Leo\_I](#):
>
> @bertschi Thanks, but that sounds way too complicated for just a mere bisection use.

Well, yes … but you can easily hide that behind a short function.  
Further, implementing bisection from scratch also needs care (see [here](https://research.google/blog/extra-extra-read-all-about-it-nearly-all-binary-searches-and-mergesorts-are-broken/) for a common bug which also applies to the code in this thread).

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [April 27, 2025, 6:37pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/12 "2025-04-27T18:37:34Z")

</div>

> [@Leo\_I](#):
>
> Hmm, doubling the amount of code just for this case is ugly to me. Besides, it seems somehow wrong to me that `lastindex` and `length`of `0:typemax(UInt))` is `0` even though iterating through this range is nonempty. Could this be considered a bug in Base Julia?

That’s an interesting question. It’s not easily fixable, since `length` would have to be changed to return either a `Int128` or longer, or a `BigInt` in this case, making it type unstable or breaking. The problem comes from the fact that julia does not use a “mathematical” integer for literals, lengths and sizes, like some languages do (cryptol springs to mind), but an ordinary bit integer.

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [April 27, 2025, 6:51pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/13 "2025-04-27T18:51:23Z")

</div>

I’ve entered an issue for the segfault from

```julia
collect(0:typemax(UInt))

```

> <https://github.com/JuliaLang/julia/issues/58245>
>
> \`\`\`
> julia\> versioninfo()
> Julia Version 1.11.5
> Commit 760b2e5b739 (2025-04-14 06:…53 UTC)
> Build Info:
> Official https://julialang.org/ release
> Platform Info:
> OS: Linux (x86\_64-linux-gnu)
> CPU: 16 × AMD Ryzen 7 2700X Eight-Core Processor
> WORD\_SIZE: 64
> LLVM: libLLVM-16.0.6 (ORCJIT, znver1)
> Threads: 16 default, 0 interactive, 8 GC (on 16 virtual cores)
> Environment:
> 
> julia\> collect(0:typemax(UInt))
> 
> \[1332714\] signal 11 (1): Segmentation fault
> in expression starting at REPL\[2\]:1
> setindex! at ./array.jl:987 \[inlined\]
> Array at ./range.jl:1375 \[inlined\]
> Array at ./boot.jl:605 \[inlined\]
> collect at ./range.jl:1380
> \`\`\`
> 
> From https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/12?u=sgaure

---

<div class="post-metadata">

**Author:** ![Leo\_I](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leo_i/32/27262_2.png) [@Leo\_I](https://discourse.julialang.org/u/Leo_I)\
**Post date:** [April 27, 2025, 7:36pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/14 "2025-04-27T19:36:43Z")

</div>

@bertschi Thank you for pointing out the insidious bug in my code: `b = (a+c)÷2` must be replaced with `b = a+(c-a)÷2` to not overflow. Appreciate that!

@sgaure Thank you for discovering even a segfault from this bug and opening an issue!

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [April 27, 2025, 8:39pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/15 "2025-04-27T20:39:10Z")

</div>

It transpired in the issue discussion that arithmetic overflow checking was intentionally removed from `length` in [deprecate unsafe\_length for length by vtjnash · Pull Request #40382 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/40382). The reason being that possibly throwing an error in such an essential function adds complexity which meddles with optimization.

So it’s probably better to work around it. (But the segfault must be fixed anyway).

---

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [April 28, 2025, 2:26pm UTC](https://discourse.julialang.org/t/built-in-binary-search-for-sorted-collections/128374/16 "2025-04-28T14:26:43Z")

</div>

> [@Leo\_I](#):
>
> gives an incorrect answer

Sorry about that, I intending to just give you a starting point, which is what I meant by “something like”. I probably should have just left the post at a pointer to the documentation. I’m glad you got a working implementation yourself. Sometimes its more expedient to implement an algorithm yourself than it is to find the right incantation of a library function.