今日は線形探索と二分探索の違いについて話していくわよ。

どちらも大事な探索手法なんだけど、初めて耳にする人にはちょっと混乱しちゃうかもしれないわね。

 

線形探索（せんけいたんさく）とは何者？？

線形探索とは、

配列やリストの端から順番に目的の値を探していく方法

よ。

例えば、0から9までの数字が入った配列がここにあるとするわ。

• 0
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

この中から「7」を見つけるために線形探索を使う場合、0からひとつずつ確認していって、最終的に「7」を見つけることができるわけ。

 

線形探索のメリット

この方法のいいところは、何といってもコードがシンプルなこと。それに、どんな順序のデータに対しても使えるわ。

 

線形探索のデメリット

線形探索は端から順番に1つずつ探すため、データの数が多くなるほど、探す時間も増えていくの。

データが n 個ある場合、最悪の場合は n 個すべてを調べることになるわ。

このような計算量を O(n) と表すのよ。

 

二分探索（にぶんたんさく）とは何者？？

二分探索とは、その名の通り、

データを半分に分割しながら探索を進める方法

よ。

ただし、データが昇順または降順に整列されている必要があるのがポイント。

 

二分探索の方法

たとえば、昇順に並んだデータから「7」を見つけたいとき、まず配列の真ん中の値を確認するの。

• もし真ん中の値が「7」なら、それでおしまい。
• 「7」が真ん中の値より小さければ、左側の半分で探索を続ける。
• 大きければ、右側の半分で探索を進めるの。

これを繰り返していけば、すぐに「7」が見つかるわ。

計算量はO(\log n)で、線形探索の O(n) よりも高速なの。

 

二分探索の条件とデメリット

でも、データがきちんと並んでいないと使えないの。準備が大変な分、適用できる問題は限られるわね。

 

線形探索と二分探索の使い分け

どちらを選ぶべきかは、データの特性や量によるわ。

 

線形探索を使うべきとき

データがランダムで整列されていないときや、データ量が少ないときによく使われるのよ。

 

二分探索を使うべきとき

一方で、データが整列されていて、量が多いときは二分探索が適しているわ。効率よく探索できるのが嬉しいわよね。

 

 

それじゃあね！