サーチ(検索)とは
サーチとは、たくさんのデータの中から目的のデータがどこにあるか調べる作業である。
リニアサーチ
リニアサーチとは、要は「力ずくの検索」のことである。線形探索という。計算量オーダはO(N)。
先頭から順番に調べていって、探している数値と同じかどうかを確認。
探している数値が見つかったら場所を返すというもの。
リニアサーチするRubyのサンプル
# -*- encoding: utf-8 -*- def lenear_search(array, target_num) array_size = array.size() for num in 0..(array_size - 1) if (target_num == array[num]) puts "一致しました!!!" p "indexは", num return num end end puts "ごめんなさい。一致しませんでした・・・" return -1 end array = []; for num in 1..300 do array << (rand() * 500).to_i end puts "配列のサイズは・・・" puts array.size() puts "---------" target_num = 95 puts "目的の数字は・・・・" puts target_num puts "---------" puts "リニアサーチを開始します!" index = lenear_search(array, target_num) puts "------" if index != -1 puts "目的の数字は・・・" puts array[index] puts "ですね?" end
lenear_searchメソッドに、配列とターゲットの数字を渡して、目的の数字がどのインデックスに存在するかを調べる。
先頭から順に力ずくで一致するかどうかを調べているのがわかる。
値が見つかった時の結果は、以下の通りになる。
配列のサイズは・・・ 300 --------- 目的の数字は・・・・ 95 --------- リニアサーチを開始します! 一致しました!!! "indexは" 145 ------ 目的の数字は・・・ 95 ですね?
値が見つからなかった時の結果は以下の通り。
配列のサイズは・・・ 300 --------- 目的の数字は・・・・ 95 --------- リニアサーチを開始します! ごめんなさい。一致しませんでした・・・ ------
勉強した本

- 作者: 紀平拓男,春日伸弥
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2011/03/30
- メディア: 単行本
- 購入: 15人 クリック: 255回
- この商品を含むブログ (31件) を見る
感謝のプログラミング
今回で感謝のプログラミングは【594時間目】
10000時間まで、あと【9406時間】