2-8 探索アルゴリズム

探索

ある値に一致するデータを探し出すこと

• 線形探索
• 2分探索

線形探索

並んでいる順に１個ずつ調べていく探索。
※1個ずつ大小を調べることで、最大値・最小値を求めるアルゴリズムも作ることができる。

計算量は、１個ずつ地道に調べていくため、平均すると(n+1)/2回（n/2程度）の計算量になり、nに比例するため、オーダはO(n)となる。

オーダについて

2分探索

大きさ順に整列されている場合に、探索対象の中央に位置する要素と比べて、1/2ずつ絞っていく探索

計算量は、1/2ずつ絞っていくため、比較回数は平均でlog₂ｎになり、それに準じてオーダはO(logn)となる。