みなさんこんにちは！おさかなです！
今回から「誰でもわかる基本情報シリーズ」というテーマで「基本情報技術者試験」に合格するための知識をご紹介していきます！
第25弾は「データの探索」について、書いていこうと思います！
それでは、レッツゴー！！！！！
・「基本情報技術者試験」を受験しようと思っている人
・「基本情報」に必要な知識を身に着けたい人
・IT初心者の人
前回の復習
前回は「その他のソート」について学習していきました！
今回は「データの探索」について見ていきましょう！
データの探索
「データの探索」とは、配列などを使って「目的のデータ」を探しだすことです。
代表的なアルゴリズムとして「線形探索法」、「2分探索法」「ハッシュ探索法」などがあります。
順番に見ていきましょう！
線形探索法(逐次探索法)
「線形探索法」とは、配列の「一番最初」から順番にデータを調べていく方法です。
0,1,2,3,4,5…と片っ端から探すイメージです。
不規則に配列されている「大量のデータ」の中から、目的のデータを探すのに適していますが、探索に「時間がかかる」のがデメリットです。
番兵法
また、「線形探索法」の中に「番兵法」を使ったものがあります。
「番兵法」とは、探したい目的のデータを配列の最後尾に追加する方法です。「番兵」には「見張り番」という意味があり、お店などの行列の最後に「最後尾」という看板を持っている係員の立ち位置をイメージするとわかりやすいです。
線形探索法の探索回数
N個のデータにおいて、線形探索法で探索した場合
・最大 … N回
・平均探索回数 … (N+1) / 2
2分探索法
「2分探索法」とは、「目的のデータ」と「配列の中央のデータ」を比較し、一致しなければその「大小関係」から、中央のデータを除いた「前半」または「後半」の範囲で同様のことを繰り返す方法です。
データが「昇順」か「降順」に並んでいるときだけ探索できます。
2分探索法の探索回数
N個のデータにおいて、2分探索法で探索した場合
(データ量が2倍になるごとに、探索回数が1回増えていきます。)
・最大比較回数 … log2N + 1 回
ハッシュ探索法
「ハッシュ探索法」とは、キーの関数値によって格納先のアドレスを算出し、直接探索する方法です。
「データの格納先」は事前に決めておき、「格納先のアドレス」は、データの値に一定の計算をして求めます。
このときに使う関数を「ハッシュ関数」といい、データの探索時も同じ「ハッシュ関数」を使います。
それから、格納先のアドレスが衝突してしまうことを「シノニム」といい、発生すると再度別の方法で「格納先のアドレス」を求める必要が出てきてしまいます。
ハッシュ探索法の探索回数
N個のデータにおいて、ハッシュ探索法で探索した場合
しっかり復習しておこう！
おさかなが参考にした「書籍」一覧↓
・(PDF・スマホ単語帳付)かんたん合格 基本情報技術者教科書 令和2年度
・令和02年 イメージ＆クレバー方式でよくわかる 栢木先生の基本情報技術者教室 情報処理技術者試験
・キタミ式イラストIT塾 基本情報技術者 令和02年 (情報処理技術者試験)
感想・まとめ
今回は「データの探索」について、書いていきました…！
いかがだったでしょうか？
それぞれの探索方法の特徴を押さえて、確実に回答できるようにしていきましょう！(おさかなもがんばります…！)
4月19日に予定されていた、「基本情報技術者試験」およびIPA主催のその他の試験は中止となりました。
詳しくはコチラをご覧ください。
※次回は「計算量」について解説していきます！
お楽しみに～！
おさかなびではプログラミング学習中の人、ブログ初心者に向けて、「デジタル時代を楽しむためのミニ知識」をご紹介しています！
ぜひ他のページも覗いてみてください…！
それでは今回はこの辺で！
ここまで読んでくださり、ありがとうございました！
おさかなでした！
【おさかなび-osakanav-】では、この記事の感想！おさかなへの応援メッセージ！おさかなに聞きたい事、質問！記事にしてほしい内容！などを大募集中！
「氏名」「メールアドレス」「内容」の3点をご記入の上「osakana1699@gmail.com」までご応募ください！
