szmlb.net

ロボット関係のメモ書き. 自分用メモに使っているので, 人に読ませることを意識せずに書きなぐります.

逐次探索 (アルゴリズムクイックリファレンス 5.1)

続いて逐次探索.
その名の通り, リストの最初から終わりまで一致するものを探索する.

計算量

  • 最良 O(1)
  • 平均 O(n)
  • 最悪 O(n)

サンプルコード

function sequentialSearch(A, t)

  for (index, value) in enumerate(A)
    if value == t
      return index
    end
  end
  return false

end

function main()

  # list to be sorted
  rng = MersenneTwister(1234);
  list_size = 1e7
  A = shuffle(rng, Vector(1:list_size))

  # Search
  search_num = list_size/2
  index_found = @time sequentialSearch(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.001650 seconds
Search for : 5000000
Found index: 2045999
Found value is ... 5000000