# Indices of intersection of two arrays

**URL:** <https://discourse.julialang.org/t/indices-of-intersection-of-two-arrays/23043>\
**Category:** General Usage\
**Tags:** arrays\
**Created:** [April 11, 2019, 4:07pm UTC](https://discourse.julialang.org/t/indices-of-intersection-of-two-arrays/23043 "2019-04-11T16:07:01Z")\
**Posts on this page:** 1\
**Showing post:** 7

<div class="post-metadata">

**Author:** ![Seif\_Shebl](https://avatars.discourse-cdn.com/v4/letter/s/eada6e/32.png) [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)\
**Post date:** [July 23, 2021, 1:00pm UTC](https://discourse.julialang.org/t/indices-of-intersection-of-two-arrays/23043/7 "2021-07-23T13:00:11Z")

</div>

You may get another 2X speedup by avoiding `push!` inside the loop and using `BitArray`s to store common indices flag instead. Although `push!` is quite efficient in Julia, using it inside hot loops can be expensive. The speedup from this change can vary depending on the ratio of common indices.

```julia
function sorted_intersect2(x::AbstractVector, y::AbstractVector)
    @assert issorted( x ) 
    @assert issorted( y ) 

    idx_common_x = falses(length(x))
    idx_common_y = falses(length(y))
    i, j = firstindex(x), firstindex(y)
    while i <= lastindex(x) && j <= lastindex(y)
        if x[i] < y[j]
            i += 1
        elseif y[j] < x[i]
            j += 1
        else
            idx_common_x[i] = true
            idx_common_y[j] = true
            i += 1
            j += 1
        end
    end
    (1:length(x))[idx_common_x], (1:length(y))[idx_common_y]
end

function sorted_intersect(x::AbstractVector, y::AbstractVector)
    @assert issorted( x )
    @assert issorted( y )

    idx_common_x = Vector{Int}()
    idx_common_y = Vector{Int}()
    i,j = firstindex(x), firstindex(y)
    while i <= lastindex(x) && j <= lastindex(y)
        if x[i] == y[j]
            push!( idx_common_x, i )
            push!( idx_common_y, j )
            i += 1
            j += 1
        elseif x[i] > y[j]
            j += 1
        else
            i += 1
        end
    end
    idx_common_x, idx_common_y
end

a = [1:1000;] #[2, 4, 6, 7, 10, 11]
b = [600:1850;] #[6, 7, 10, 11, 13, 15, 17, 19, 21, 23]
@assert sorted_intersect(a, b) == sorted_intersect2(a, b)
@btime (findall(in($b),$a) , findall(in($a),$b))
  8.767 μs (10 allocations: 15.12 KiB)
@btime sorted_intersect($a, $b)
  6.700 μs (10 allocations: 15.12 KiB)
@btime sorted_intersect2($a, $b)
  3.263 μs (6 allocations: 7.12 KiB)

```

---

_[View the full topic](https://discourse.julialang.org/t/indices-of-intersection-of-two-arrays/23043)._