RSS
Programming Place Plus トップページ – アルゴリズムとデータ構造編
この章の概要です。
関連する話題が、以下のページにあります。
この章では、二分探索（バイナリサーチ）というアルゴリズムを紹介します。
二分探索は非常に重要度の高いアルゴリズムです。このアルゴリズムの考え方は、探索に限らず、さまざまな問題の解決に応用できるからです。
二分探索を使って探索を行うには、対象のデータの集まりがソート済みでなければならないという前提条件があります。
二分探索の手順を説明します。ここでは、対象のデータは、要素数 100 の配列 array で、昇順にソートされています。探索したい値は 70 だとします。
まず、データの集まりの中央にあたる場所を調べます。要素数 100 ですから、添字の範囲は 0～99 なので、(0 + 99) / 2 のように計算すれば、中央の添字が分かります。この計算結果は 49 になるので、array[49] を調べます。もし、array[49] の値が目的の値と一致していたら、この時点で探索完了です。
array[49] に 40 が格納されていたとしましょう。array は昇順にソートされているのですから、目的の値である 70 が array の中に存在するのだとすれば、array[49] よりも後ろ側にあることがわかります。そこで今度は、array[50]～array[99] の中央にあたる場所を調べることにします。(50 + 99) / 2 により、74 の位置を調べればいいとわかるので、array[74] の値を調べます。ここに目的の値があれば完了です。
array[74] には 90 が格納されていたとします。一致しなかったものの、これで目的の値が存在しているとすれば、array[74] より手前側にあることがわかります。また、array[49] より後ろであることも分かっています。なので、次に探す場所は (50 + 73) / 2 として、array[61] です。
・・・といった手順を繰り返していくと、どこかで目的の値が発見されるか、あるいは最終的に行き着いた場所でも見つからないかのどちらかです。
このように、二分探索は、半分に分けていく過程を繰り返します。要素を１つ比較するたびに、探索する対象範囲が半分に減っていくので、線形探索と比べて非常に高速に絞り込まれていきます。
しかし、二分探索には大きな問題が２つあります。
まず、対象のデータ列が、各要素に直接アクセスできなければなりません。これは、「中央の位置」が一発で参照できなければ、性能が極端に低下するからです。中央を探すたびにいちいち要素を辿らなければならない連結リストのようなデータ構造は、二分探索には向いていません。
また、冒頭でも触れたとおり、二分探索は、対象のデータ列がソートされていなければなりません。プログラムの実行開始前の時点でソート済みにしておけるならまったく問題ありませんが、つねに変化し続けるデータ列を対象とする場合、ソートにかかる時間が無視できなくなるかもしれません。
その場合は、二分探索木（【データ構造】第８章）を検討しましょう。
昇順にソートされた配列を対象にして、二分探索を実装してみます。
#include <stdio.h>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
static int* binary_search(int* array, size_t size, int value);
int main(void)
{
int array[] = { -4, -1, 0, 3, 7, 9, 16 };
for(int i = -5; i <= 5; ++i){
int* p = binary_search( array, SIZE_OF_ARRAY(array), i );
if( p == NULL ){
printf( "%d: 見つかりませんでした。\n", i );
}
else{
printf( "%d: 見つかりました。\n", i );
}
}
return 0;
}
/*
二分探索
対象の配列array は昇順にソートされていることを前提としている。
*/
int* binary_search(int* array, size_t size, int value)
{
int lower = 0; // 探索範囲の下限の添字
int upper = (int)size - 1; // 探索範囲の上限の添字
while( lower <= upper ){ // 上限と下限が逆転したら終わり
// 中央の位置を求める
int mid = (lower + upper) / 2;
if( array[mid] == value ){
return &array[mid]; // 目的の値を見つけたら終わり
}
else if( array[mid] < value ){
lower = mid + 1; // 次は中央より後ろを調べるため、下限を変更
}
else{
upper = mid - 1; // 次は中央より手前を調べるため、上限を変更
}
}
return NULL;
}実行結果：
-5: 見つかりませんでした。
-4: 見つかりました。
-3: 見つかりませんでした。
-2: 見つかりませんでした。
-1: 見つかりました。
0: 見つかりました。
1: 見つかりませんでした。
2: 見つかりませんでした。
3: 見つかりました。
4: 見つかりませんでした。
5: 見つかりませんでした。基本的には冒頭の説明どおりの実装です。探索する範囲の先頭と末尾の位置を、変数 lower と upper で管理しています。両者の中間の位置を計算して（変数 mid）、その位置を調べることを繰り返します。
終了判定については、目的の値が見つかったのなら、その時点で終了するだけです。目的の値が見つからなかったことを検出するには、探索範囲の上限と下限が逆転してしまったかどうかを調べます。
なお、この実装は、対象のデータ列に値の重複があり、探索したい値がまさにそれらの値である場合に、どの要素を見つけ出すか予想できません。これはまったく気にする必要がない場合も多いですが、もし問題になるのであれば、多少工夫を加えることで解決できます。この話題はあらためて取り上げます。
二分探索の実際の性能を確認しておきましょう。シンプルな線形探索と比較してみます。
#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"
#define ARRAY_SIZE (1000000)
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
static int* linear_search(int* array, size_t size, int value);
static int* binary_search(int* array, size_t size, int value);
int main(void)
{
static int array[ARRAY_SIZE];
for( int i = 0; i < ARRAY_SIZE; ++i ){
array[i] = i;
}
PPP_CHECK_PERFORM_BEGIN(10000);
linear_search( array, SIZE_OF_ARRAY(array), rand() * (ARRAY_SIZE / RAND_MAX) );
PPP_CHECK_PERFORM_END("linear_search");
PPP_CHECK_PERFORM_BEGIN(10000);
binary_search( array, SIZE_OF_ARRAY(array), rand() * (ARRAY_SIZE / RAND_MAX) );
PPP_CHECK_PERFORM_END("binary_search");
return 0;
}
/*
線形探索
*/
int* linear_search(int* array, size_t size, int value)
{
for( size_t i = 0; i < size; ++i ){
if( array[i] == value ){
return &array[i];
}
}
return NULL;
}
/*
二分探索
対象の配列array は昇順にソートされていることを前提としている。
*/
int* binary_search(int* array, size_t size, int value)
{
int lower = 0; // 探索範囲の下限の添字
int upper = (int)size - 1; // 探索範囲の上限の添字
while( lower <= upper ){ // 上限と下限が逆転したら終わり
// 中央の位置を求める
int mid = (lower + upper) / 2;
if( array[mid] == value ){
return &array[mid]; // 目的の値を見つけたら終わり
}
else if( array[mid] < value ){
lower = mid + 1; // 次は中央より後ろを調べるため、下限を変更
}
else{
upper = mid - 1; // 次は中央より手前を調べるため、上限を変更
}
}
return NULL;
}0 から順番に 1 ずつ増加する値が格納された配列（つまり昇順にソートされている）から、ランダムで決定した値を探索することを 10000回ずつ行っています。
データ件数ごとの比較結果はこうなりました。
| データ件数 line | ar_search bina | ry_search |
|---|---|---|
| 10000個 | 0.001秒 0 | .002秒 |
| 100000個 | 0.970秒 0 | .003秒 |
| 1000000個 | 9.636秒 0 | .006秒 |
データ件数が少ないと、差はほとんどありません。処理自体が複雑な分（ループの内側の内容）、むしろ二分探索のほうがやや遅くなる傾向すらあります。
しかし、データ件数が増加したときの処理時間の増え方は比較にならないほどです。これはたとえば、データ件数が 100000個のとき、線形探索では平均して 50000回の比較が必要であるのに対し、二分探索なら平均して 17回程度の比較で済んでしまうからです。１回の比較のたびに、対象範囲が半分になる特性がこれだけの効率の高さを生み出しています。
計算量でいうと、線形探索が O(n) であるのに対し、二分探索は O(log n) です。
実際のところ、二分探索がいつも線形探索より高速かというと、そういうわけではありません。先ほどのプログラムで、探す値を 0（配列の先頭の値）に変更したら、線形探索はいつも１回目の比較で要素を発見できますから、つねに最速の速度が出ます。二分探索では、要素を絞り込んでいって、ようやく array[0] に到達するので、遠回りをしなければならず、かえって遅くなります。
実際に、0 を探すようにして試すと、次の結果が得られました（速すぎて計測できないので、試行回数（PPP_CHECK_PERFORM_BEGINマクロに渡す値）を 1000回に増やしています）
| データ件数 line | ar_search bina | ry_search |
|---|---|---|
| 10000個 | 0.224秒 0 | .796秒 |
| 100000個 | 0.223秒 0 | .976秒 |
| 1000000個 | 0.227秒 1 | .075秒 |
線形探索のほうは、データ件数が増えても、array[0] を見るだけなので、ほとんど変化しません。二分探索のほうは、比較位置（変数 mid）が 0 に行き着くまでのステップ数が変わるので、データ件数によって少し差が出ます。ともかく、こういうケースでは、二分探索のほうが遅くなります。
二分探索は線形探索よりも、“つねに速い” のではなく “平均的に速い” ということです。データ件数がある程度大きければ（1000個程度あれば十分に大きいといえます）、通常は二分探索を選んだ方が良い性能を得られるでしょう。
ここまでに取り上げた二分探索の実装は、対象のデータ列の中に、目的の値が重複しているとき、どの要素を見つけ出すか、予測がつきません。
まずは試してみましょう。
#include <stdio.h>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
static int* binary_search(int* array, size_t size, int value);
int main(void)
{
int array[] = { 1, 2, 2, 4, 4, 7, 7, 7, 9 };
int* p = binary_search( array, SIZE_OF_ARRAY(array), 7 );
if( p == NULL ){
puts( "見つかりませんでした。" );
}
else{
printf( "見つかりました。(array[%td])\n", p - array );
}
return 0;
}
/*
二分探索
対象の配列array は昇順にソートされていることを前提としている。
*/
int* binary_search(int* array, size_t size, int value)
{
int lower = 0; // 探索範囲の下限の添字
int upper = (int)size - 1; // 探索範囲の上限の添字
while( lower <= upper ){ // 上限と下限が逆転したら終わり
// 中央の位置を求める
int mid = (lower + upper) / 2;
if( array[mid] == value ){
return &array[mid]; // 目的の値を見つけたら終わり
}
else if( array[mid] < value ){
lower = mid + 1; // 次は中央より後ろを調べるため、下限を変更
}
else{
upper = mid - 1; // 次は中央より手前を調べるため、上限を変更
}
}
return NULL;
}実行結果：
見つかりました。(array[6])対象の配列には、探し出したい値である 7 が、全部で 3つ格納されています。それぞれ、array[5], array[6], array[7] にありますが、実行結果によると array[6] を発見したようです。
同じデータ列で、同じ実装の二分探索を使っているかぎりは、結果は同じになりますから、完全に不定だというわけではないですが、少なくとも法則はありません。もしこれが線形探索であれば、先頭から順番に探すので、必ず array[5] を発見するでしょう。
このように、線形探索ならば、確実に先頭に近いものを発見するのに対し、（ここまでの）二分探索の実装ではそのような保証がありません。
しかし二分探索であっても、実装を工夫すれば、発見する要素を、先頭に近いものか末尾に近いものかを保証できます。次の二分探索の実装では、要素が発見できた場合には必ず先頭に近い要素を返します。
#include <stdio.h>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
static int* binary_search(int* array, size_t size, int value);
int main(void)
{
int array[] = { 1, 2, 2, 4, 4, 7, 7, 7, 9 };
int* p = binary_search( array, SIZE_OF_ARRAY(array), 7 );
if( p == NULL ){
puts( "見つかりませんでした。" );
}
else{
printf( "見つかりました。(array[%td])\n", p - array );
}
return 0;
}
/*
二分探索
対象の配列array は昇順にソートされていることを前提としている。
*/
int* binary_search(int* array, size_t size, int value)
{
int lower = 0; // 探索範囲の下限の添字
int upper = (int)size; // 探索範囲の上限の添字 + 1
while( lower < upper ){ // 上限と下限が逆転したら終わり
// 中央の位置を求める
int mid = (lower + upper) / 2;
if( array[mid] < value ){
lower = mid + 1; // 次は中央より後ろを調べるため、下限を変更
}
else{
// ここに来るケースには、目的の値と同じ場合を含んでいる
// そのため、upper = mid - 1; ではない
upper = mid; // 次は中央より手前を調べるため、上限を変更
}
}
// 目的の値を発見している場合も、発見できなかった場合も、
// ここに来ることになるので、ここで最終的な確認を行う。
// lower == upper は、array が空の場合への備え。
if (lower == upper && array[lower] == value){
return &array[lower];
}
return NULL;
}実行結果：
見つかりました。(array[5])変わったのは５箇所です。
１つ目は、変数upper の初期値です。これまでは、探索範囲の上限の添字でしたが、今回はそれにさらに +1 しています。
２つ目は、while文の条件式で、<= が < になっています。すなわち、現在の注目位置にある値と、目的の値が同じ場合にもループを抜け出すようになりました。
３つ目は、目的の値との一致を調べる if文がなくなったことです。
４つ目は、else句のところに来るケースに、“目的の値と一致している場合” が加わったため、行うべき処理が変化しています。以前の方法だと、upper = mid - 1; としていましたが、減算がなくなっています。減算させてしまうと、目的の値と一致している場合に、それが探索範囲から外れてしまいます。
５つ目は、while文を抜け出したところで、目的の値との一致を見る if文が追加されたことです。ここで最終的に、探索の成否が確定します。
結局のところ、目的の値と一致している間はループを終わらせず、一致する可能性が完全になくなるまでループを続行するように変わったということです。こうすると、目的の値が複数並んでいたとき、注目位置が少しずつ手前の方へ移動してきます（一致しているかぎり、else句のところに入るので、upper の値が小さくなっていくから。結果、mid の値も少しずつ小さくなる）。
分かりづらいですが、配列の中身をすべて同じ値にして、その値を探し出すようすると多少理解しやすいかもしれません。次のプログラムを試してみましょう。
#include <limits.h>
#include <stdio.h>
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
static int* binary_search(int* array, size_t size, int value);
int main(void)
{
int array[] = { 7, 7, 7, 7, 7, 7, 7, 7, 7 };
int* p = binary_search( array, SIZE_OF_ARRAY(array), 7 );
if( p == NULL ){
puts( "見つかりませんでした。" );
}
else{
printf( "見つかりました。(array[%td])\n", p - array );
}
return 0;
}
/*
二分探索
対象の配列array は昇順にソートされていることを前提としている。
*/
int* binary_search(int* array, size_t size, int value)
{
int lower = 0; // 探索範囲の下限の添字
int upper = (int)size; // 探索範囲の上限の添字 + 1
while( lower < upper ){ // 上限と下限が逆転したら終わり
printf( "現在の探索範囲: [%d～%d] 中央: %d\n", lower, upper, (lower + upper) / 2 );
for( size_t i = 0; i < size; ++i ){
if( lower <= i && i <= upper ){
printf( "%d ", array[i] );
}
else{
printf( " " );
}
}
printf( "\n" );
// 中央の位置を求める
int mid = (lower + upper) / 2;
if( array[mid] < value ){
lower = mid + 1; // 次は中央より後ろを調べるため、下限を変更
}
else{
// ここに来るケースには、目的の値と同じ場合を含んでいる
// そのため、upper = mid - 1; ではない
upper = mid; // 次は中央より手前を調べるため、上限を変更
}
}
// 目的の値を発見している場合も、発見できなかった場合も、
// ここに来ることになるので、ここで最終的な確認を行う。
// lower == upper は、array が空の場合への備え。
if (lower == upper && array[lower] == value){
return &array[lower];
}
return NULL;
}実行結果：
現在の探索範囲: [0～9] 中央: 4
7 7 7 7 7 7 7 7 7
現在の探索範囲: [0～4] 中央: 2
7 7 7 7 7
現在の探索範囲: [0～2] 中央: 1
7 7 7
現在の探索範囲: [0～1] 中央: 0
7 7
見つかりました。(array[0])注目位置（中央: 4 のように出力されています）が少しずつ手前側へ移動していく様子が分かります。
二分探索の計算量は O(log n)で、効率的です。実装が困難というわけでもないので、非常に利用価値の高いアルゴリズムです。
対象のデータ列の要素に直接アクセスできないと効率が大きく低下する点と、ソート済みでなければならない点が、二分探索の欠点と言えます。
ソート済みでなければならないという点については、探索直前で一気にソートする考え方と、データ構造の工夫によって、つねにソートされた状態を保っておくという考え方とがあります。
前者の考え方の場合、ソート作業で効率が落ちることになります。特に、すでにソート済みであった場合に、無駄にソート作業が走るのは非効率でしょう（すでにソート済みであることが多いときのソートには、挿入ソート（【整列】第４章）を選択しましょう）。
後者の考え方の場合、配列への挿入や削除の作業の計算量は O(n) なので（【データ構造】第１章）、この部分で全体的な効率が落ちます。配列への挿入や削除の作業で効率を落とすことが許されない場合、二分探索木（【データ構造】第８章）のような方法を検討するといいでしょう。
問題① 対象の配列が降順にソートされている場合の二分探索関数を作成してください。
問題② 対象の配列の要素が文字列の場合（つまり、文字列の配列）でも二分探索が使えますか？ 可能ならば実装してみてください。
問題③ 引数に、配列と探索範囲の上限と下限、探索する値を指定する形で二分探索関数を作成してください。
’2017/2/26 「値が重複している場合」のサンプルプログラムの実行結果が間違っていたのを修正。
≪さらに古い更新履歴を展開する≫
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| Twitter でツイート | Twitter をフォロー | LINE で送る |
|
RSS
|
管理者情報 | プライバシーポリシー |