Mercurial > lbo > hg > juliaplay
view julia/matrixsearch.jl @ 6:661876a2502e
py: dp
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 19 Feb 2023 12:50:44 +0100 |
parents | c1db337c15be |
children |
line wrap: on
line source
function generate_sorted_matrix(m, n)::Matrix{Int} v = abs.(rand(Int, m*n)) .% 1000 sort!(v) reshape(v, m, n) end const Option{T} = Union{Some{T}, Nothing} function find_in_sorted_array(V::AbstractVector{Int}, n::Int)::Option{Int} lo, mid, hi = 1, round(Int, length(V)/2), length(V) while lo < hi if n < V[mid] hi = mid-1 mid = round(Int, (lo+hi)/2) continue elseif n > V[mid] lo = mid+1 mid = round(Int, (lo+hi)/2) continue elseif n == V[mid] return Some(mid) end @assert false "if exhausted" end V[mid] == n ? Some(mid) : nothing end function find_in_sorted_matrix(M::Matrix, n::Int)::Option{Tuple{Int, Int}} r, c = size(M) # 1. Find column lo, mid, hi = 1, round(Int, c/2), c while lo < hi if n < M[begin, mid] hi = mid-1 mid = round(Int, (lo+hi)/2) continue elseif n > M[end, mid] lo = mid+1 mid = round(Int, (lo+hi)/2) continue else break end end # 2. Find element in_array = find_in_sorted_array((@view M[:,mid]), n) if isnothing(in_array) nothing else Some((mid, something(in_array))) end end