f:id:shogonir:20200524000226p:plain

概要

二分探索と線形探索は、リスト探索という問題を解く方法（アルゴリズム）の一種。
リスト探索という問題は、基本的で理解しやすい問題です。
そのため、アルゴリズムの重要性を学ぶのに最適だと思います。

プログラマーでもアルゴリズムを意識する機会は少ないと思います。
しかし、前提条件を正しく判断してアルゴリズムを選択すると、
問題を解く時間を著しく削減できることがあります。

この記事では、リスト探索という問題を例にとって説明したいと思います。

動画

この記事の解説をした動画が4本ありますので、そちらもご確認ください。

youtu.be

1. リスト探索

リスト探索とは、リストから特定の要素を探すという問題です。
これだけだと曖昧なので、もう少し厳密に定義します。

入力は、探したい要素 e と長さ n のリスト a とします。
a の先頭から i 番目の要素を a[i] と表すこととします。
先頭の要素は 0 番目、最後の要素は n-1 番目とします。

出力は、要素 e が a の先頭から何番目に存在するかを返す。
もし要素 e が a の中に存在しない場合は -1 を返す。

文字を下の表にまとめます。

文字	意味
`e`	探したい要素
`a`	リスト
`n`	リストの長さ
`a[i]`	リスト `a` の `i` 番目の要素

入力と、それに対する正しい出力の例をかきます。

(1) 
入力：e = 2, n = 4, a = (1, 1, 2, 3)
出力：2

(2)
入力：e = 1, n = 4, a = (1, 1, 2, 3)
出力：0 or 1

(3)
入力：e = 4, n = 4, a = (1, 1, 2, 3)
出力：-1

2. 二分探索と線形探索の性質

二分探索と線形探索の性質を、前提条件と速さについて比較したいと思います。

アルゴリズム	前提条件	問題を解く速さ
線形探索	とくになし	比較的遅い
二分探索	リストが整列済み	比較的速い

線形探索は、シンプルなアルゴリズムなので前提条件がありません。
その代わり探索に時間がかかるので、大きいリストの探索に不向きです。

二分探索は、入力のリストが整列済みである必要があります。
整列済みとは、リスト内の要素が昇順（小さいものから大きいものに並んでいる）か、
降順（昇順の逆）であることです。
しかし、速さに関しては二分探索の方がかなり速いです。

この性質を知っているだけでも、リストが整列済みであれば二分探索を使って、
そうでなければ線形探索を使うのが良いということがわかります。

3. 線形探索

線形探索のアルゴリズムは非常にシンプルで、先頭から順番に見ていくというものです。

手順は次のようになります。

`linear_search(e, a, n)`

i を 0 とする
a[i] が e と等しければ i を返して終了、そうでなければ手順3に進む
i に 1 を足して i が n 以上であれば -1 を返して終了、そうでなければ手順2に戻る

具体的に手順に沿って問題を解いてみます。

(1) 探索対象がリストに含まれる場合
入力：e = 4, n = 5, a = (1, 5, 2, 4, 3)

1. リストの0番目の要素 1 は e=4 とは異なる
2. リストの1番目の要素 5 は e=4 とは異なる
3. リストの2番目の要素 2 は e=4 とは異なる
4. リストの3番目の要素 4 は e=4 と等しい、3番目に探索対象があった



(2) 探索対象がリストに含まれない場合
入力：e = 0, n = 5, a = (1, 5, 2, 4, 3)

1. リストの0番目の要素 1 は e=0 とは異なる
2. リストの1番目の要素 5 は e=0 とは異なる
3. リストの2番目の要素 2 は e=0 とは異なる
4. リストの3番目の要素 4 は e=0 とは異なる
5. リストの4番目の要素 3 は e=0 とは異なる
6. 探索対象の要素を全て探索した、探索対象は存在しなかった

4. 二分探索

二分探索は、リストの真ん中の要素を見ることで左半分か右半分のどちらかを探索対象にする手法です。
二分探索の前提条件は、リストが昇順か降順に整列済みであることですが、
ここではリストが昇順に整列されているとして説明を進めます。

まず具体例から説明します。

(1) 探索対象要素がリストに含まれる場合
入力：e = 2, n = 7, a = (1, 1, 2, 3, 5, 8, 13)

1. 探索対象リスト = (1, 1, 2, 3, 5, 8, 13)
   真ん中の要素 = 3
   3 > e = 2
   次の探索対象リストは左半分
2. 探索対象リスト = (1, 1, 2)
   真ん中の要素 = 1
   1 < e = 2
   次の探索対象リストは右半分
3. 探索対象リスト = (2)
   真ん中の要素 = 2
   2 = e = 2
   探索対象要素は2番目で見つかった



(2) 探索対象要素がリストに含まれない場合
入力：e = 0, n = 6, a = (1, 1, 2, 3, 5, 8)

1. 探索対象リスト = (1, 1, 2, 3, 5, 8)
   真ん中の要素 = 2
   2 > e = 0
   次の探索対象リストは左半分
2. 探索対象リスト = (1, 1)
   真ん中の要素 = 1
   1 > e = 0
   次の探索対象リストは左半分
3. 探索対象リスト = ()
   真ん中の要素 = なし
   探索対象要素はリストの中に見つからなかった

二分探索は、受け取ったリストの半分をまた二分探索するので、
入力が少し変わりますがリストを受け取っていることに変わりはありません。
線形探索の入力は e, a, n で、リスト a の 0 番目から n-1 番目が探索対象だったのに対し、
二分探索の入力は e, a, imin, imax で、 a の imin 番目から imax 番目が探索対象です。

手順は次のようになります。

`binary_search(e, a, imin, imax)`

もし imax < imin であれば -1 を返す。そうでなければ手順2に進む
リストの探索範囲の真ん中の番号を imid <- imin + (imax - imin) / 2 とし、真ん中の要素を mid <- a[imid] とする
もし mid > e であれば現在の探索範囲の左半分が次の探索範囲となるため binary_search(e, a, imin, imid - 1) を返す。そうでなければ手順4に進む
もし mid < e であれば現在の探索範囲の右半分が次の探索範囲となるため binary_search(e, a, imid + 1, imax) を返す。そうでなければ手順5に進む
mid = e であるため、 imid を返す

5. 問題を解く速さを比較する

線形探索と二分探索の問題を解く速さを比較するために、両者のアルゴリズムの共通点と相違点を考えてみたいと思います。

共通点は「要素を比較することで探索範囲を狭めていく」ということです。
両者のアルゴリズムは共に、 a[i] と e を比較して探索範囲を狭めます。

相違点は「前提条件と、探索範囲の狭め方」です。
特に探索範囲の狭め方は、問題を解く速さを考える際に重要です。
なぜなら、最悪でも探索範囲が要素数が 1 になれば探索という問題は解き終わるからです。

ではここで、比較の回数と、その時の探索範囲を比較してみましょう。
ここからは最悪の場合、つまり探している要素がなかなか見つからない場合を考えます。
線形探索も二分探索も、最悪の場合は探したい要素がリストに無い場合か、末尾に存在する場合です。

要素数16のリストを線形探索した場合

比較の回数	探索範囲の要素数
0	16
1	15
2	14
...	...
16	0

要素数16のリストを二分探索した場合

比較の回数	探索範囲の要素数
0	16
1	8
2	4
...	...
5	0

探索範囲の要素数が 0 になるまでの比較回数に大きく差が出ました。
線形探索は 16 回で、二分探索は 5 回です。

この比較回数の差は、リストの要素数が増えれば増えるほど大きくなります。
たとえば要素数が 1024 であればどうなるか確認します。線形探索は 1024 回比較し、二分探索は 11 回比較します。

このように比較回数が大きく異なるのは、探索範囲の狭め方にあります。
線形探索は 1 回の比較で、探索範囲の要素数を 1 減らすことができます。
二分探索は 1 回の比較で、探索範囲の要素数を半分に減らすことができます。
リストの要素数が大きければ大きいほど、この効果の差は開きます。
これが原因で、二分探索の方が線形探索よりも問題を速く解くことができます。

6. 疑問

アルゴリズムの速さを数学的に表現できないの？
- オーダー記法があります（記事にします）
  - 整列されてないリストを探索する場合、どちらが速い？

これらの疑問を解消してくれるオーダー記法については別の記事を書きたいと思います。

shogonir blog

二分探索と線形探索のアルゴリズム

概要

動画

目次