szmlb.net

tips for robotics

二分探索 (アルゴリズムクイックリファレンス 5.2)

続いて二分探索.
リストの中央値の値と探索したい値を大小比較して, 中央値が大きければ, 中央値より小さい領域を探索. 大きければ, 中央値より大きい領域を探索. この処理を繰り返す. 二分探索実行時にはリストは整列されている必要がある.

計算量

  • 最良 O(1)
  • 平均 O(log n)
  • 最悪 O(log n)
function binarySearch(A, t)

  low = 1
  high = length(A)
  while low <= high
    mid = Int(round((low + high) / 2))
    if t == A[mid]
      return mid
    elseif t < A[mid]
      high = mid - 1
    elseif t > A[mid]
      low = mid + 1
    end
  end
  return false

end

function main()

  # list to be sorted
  rng = MersenneTwister(1234);
  list_size = 1e7
  A = Vector(1:list_size) # The list is to be sorted for binary search

  # Search
  search_num = 3000
  index_found = @time binarySearch(A, search_num)

  print("Search for : ")
  println(search_num)

  print("Found index: ")
  println(index_found)

  print("Found value is ... ")
  println(A[index_found])

end

if contains(@__FILE__, PROGRAM_FILE)
    main()
end

実行結果

0.000010 seconds
Search for : 3000
Found index: 3000
Found value is ... 3000.0