【誰でもわかる基本情報シリーズ】25.「データの探索」

テクノロジー
スポンサーリンク

みなさんこんにちは!おさかなです!

今回から「誰でもわかる基本情報シリーズ」というテーマで「基本情報技術者試験」に合格するための知識をご紹介していきます!

第25弾は「データの探索」について、書いていこうと思います!

それでは、レッツゴー!!!!!

想定読者
・「基本情報技術者試験」を受験しようと思っている人
・「基本情報」に必要な知識を身に着けたい人
・IT初心者の人

前回の復習

前回は「その他のソート」について学習していきました!

【誰でもわかる基本情報シリーズ】24.「その他のソート」
みなさんこんにちは!おさかなです! 今回から「誰でもわかる基本情報シリーズ」というテーマで「基本情報技術者試験」に合格するための知識をご紹介していきます! 第24弾は「その他のソート」について、書いていこうと思います! そ...

今回は「データの探索」について見ていきましょう!

データの探索

データの探索」とは、配列などを使って「目的のデータ」を探しだすことです。
代表的なアルゴリズムとして「線形探索法」、「2分探索法」「ハッシュ探索法」などがあります。
順番に見ていきましょう!

線形探索法(逐次探索法)

線形探索法」とは、配列の「一番最初」から順番にデータを調べていく方法です。
0,1,2,3,4,5…と片っ端から探すイメージです。

不規則に配列されている「大量のデータ」の中から、目的のデータを探すのに適していますが、探索に「時間がかかる」のがデメリットです。

番兵法

また、「線形探索法」の中に「番兵法」を使ったものがあります。
番兵法」とは、探したい目的のデータを配列の最後尾に追加する方法です。「番兵」には「見張り番」という意味があり、お店などの行列の最後に「最後尾」という看板を持っている係員の立ち位置をイメージするとわかりやすいです。

線形探索法の探索回数

N個のデータにおいて、線形探索法で探索した場合

・最小 … 1回
・最大 … N回
・平均探索回数 … (N+1) / 2

2分探索法

2分探索法」とは、「目的のデータ」と「配列の中央のデータ」を比較し、一致しなければその「大小関係」から、中央のデータを除いた「前半」または「後半」の範囲で同様のことを繰り返す方法です。

データが「昇順」か「降順」に並んでいるときだけ探索できます。

2分探索法の探索回数

N個のデータにおいて、2分探索法で探索した場合
(データ量が2倍になるごとに、探索回数が1回増えていきます。)

・平均比較回数 … log2N回
・最大比較回数 … log2N + 1 回

ハッシュ探索法

ハッシュ探索法」とは、キーの関数値によって格納先のアドレスを算出し、直接探索する方法です。

データの格納先」は事前に決めておき、「格納先のアドレス」は、データの値に一定の計算をして求めます。
このときに使う関数を「ハッシュ関数」といい、データの探索時も同じ「ハッシュ関数」を使います。

それから、格納先のアドレスが衝突してしまうことを「シノニム」といい、発生すると再度別の方法で「格納先のアドレス」を求める必要が出てきてしまいます。

ハッシュ探索法の探索回数

N個のデータにおいて、ハッシュ探索法で探索した場合

・「一様分布」の場合 … 1回
一様分布」とは全ての事象が起こる確率が一定である確率分布のことで、「サイコロ」をイメージするとわかりやすいです。
おさかな
おさかな

しっかり復習しておこう!

おさかなが参考にした「書籍」一覧↓

(PDF・スマホ単語帳付)かんたん合格 基本情報技術者教科書 令和2年度

令和02年 イメージ&クレバー方式でよくわかる 栢木先生の基本情報技術者教室 情報処理技術者試験

キタミ式イラストIT塾 基本情報技術者 令和02年 (情報処理技術者試験)

令和02年【春期】【秋期】 基本情報技術者 合格教本

感想・まとめ

今回は「データの探索」について、書いていきました…!

いかがだったでしょうか?

それぞれの探索方法の特徴を押さえて、確実に回答できるようにしていきましょう!(おさかなもがんばります…!)

おさかな
おさかな

4月19日に予定されていた、「基本情報技術者試験」およびIPA主催のその他の試験は中止となりました。
詳しくはコチラをご覧ください。

※次回は「計算量」について解説していきます!

404 NOT FOUND |   
デジタル時代を楽しむためのミニ知識をご紹介しています!

お楽しみに~!

おさかなびではプログラミング学習中の人、ブログ初心者に向けて、「デジタル時代を楽しむためのミニ知識」をご紹介しています!
ぜひ他のページも覗いてみてください…!

それでは今回はこの辺で!

ここまで読んでくださり、ありがとうございました!

おさかなでした!

【おさかなび-osakanav-】では、この記事の感想!おさかなへの応援メッセージ!おさかなに聞きたい事、質問!記事にしてほしい内容!などを大募集中!

「氏名」「メールアドレス」「内容」の3点をご記入の上「osakana1699@gmail.com」までご応募ください!

タイトルとURLをコピーしました