# Chapter16-8 「データを探索するアルゴリズム」

## 8/10(火)

###### tags:`基本情報技術`

さつき：
* 線形探索法
* 先頭から順番に一致するかみていく
* 効率面で非常にイケてない。
* 2分探索法
* あらかじめデータ群が昇順または降順に並んでいる、というふうに規則性を持つ場合。
* データのかたまりを分ける。
* データの真ん中と比較し、どのかたまりに求めるデータがあるか絞り込んでいく。
* ハッシュ法
* ハッシュ関数...一定の計算式のこと
* データを格納するときに、計算式で求めた位置へと格納しておくので、参照するようにしてください。
* 各アルゴリズムにおける探索回数
* 線形探索法...最小と最大の平均値
* 2分探索法...log2n
* ハッシュ法...１回
* 過去問
* 問1...OK
* 2分探索法は、必ずしも線形探索法より早く処理できるわけではない。データ列の先頭に検索する対象データがある場合、線形探索の方が早く探索できる。
* 問2...OK
* 格納場所の衝突が生じる可能性がある。

にわ：
- 読み込み
* データを探索するアルゴリズム
* 線形探索法
* 先頭から順に探索
* 2分探索法
* データ群が昇順である、など規則性を持っている場合は使える。真ん中より大きい・小さいなど、探索対象を2つに分類して、2分の1ずつ削り落としながら探索していく。
* ハッシュ法
* データ格納時に「ハッシュ関数」という一定の計算式を使って特定の位置に格納し、同じハッシュ関数を使ってデータの位置を算出する。
* 各アルゴリズムにおける探索回数
* 線形探索法：（目的のデータが最初にある場合 + 最後にある場合）の平均 なので、(1+n)/2 回。
* 2分探索法：データ件数をnとして、log2n
* ハッシュ法：1回
- 過去問
* 問１：OK
* 「常に」って見落としがちなやつ。
* 問２：OK

ちさと：
* データを探索
* 線形探索法：先頭から順に見ていく
* ２分探索法：データが昇順、降順に並んでいるなど規則性があるときに使える。
* ハッシュ法：ハッシュ関数（一定の計算式）を使ってデータの格納位置を出す
* 探索回数
* 線形探索法
* 目的のデータが先頭にある場合：最小となる１回
* 末尾にある場合：最大となるn回
* 平均は（１＋n）÷２
* ２分探索法
* n個のデータの２分探索：log2n
* logは何乗すればいいかを表す数
* ハッシュ法
* １回
* 過去問
* 問１：おk
* 問２：おk

まい：

* データを探索するアルゴリズム
* 探索: 目的のデータを探し当てる処理
* 線形探索法: 先頭から順に探索
* 平均探索回数 (1 + n) / 2
* 2分探索法: ソートされてる場合は効率よく処理できる
* 平均探索回数 log2n
* nは2の何乗か？の意味
* log2n + 1 = 最大探索回数
* ハッシュ法: ハッシュ関数(一定の計算式)を用いてデータ格納位置を算出
* シノニム: 計算の結果が重複、異なるレコードが同じアドレスで衝突
* 平均探索回数(シノニムを無視していい場合) 1

* 練習問題
* 問1 ok
* 問2 ok