バイナリサーチ

binary search: 二分探索

何度半分にすれば要素数が1になるか

$ N\times\left(\frac{1}{2}\right)^x = 1

$ \iff x = \log_2N

与える配列の要素がソートされていれば使える

code:jl

function binary_search(A::Vector, v)

head = 1

tail = length(A)

while head <= tail

middle = (head + tail) ÷ 2

return println("見つかる")

head = middle + 1

else

tail = middle - 1

end

end

return println("見つからない")

end

binary_search(A, 123456)

binary_search(A, 1000001)

長大な配列に利用しない場合なら問題ない

code:jl