RSS
二分探索 | Programming Place Plus アルゴリズムとデータ構造編【探索アルゴリズム】 第４章
Programming Place Plus トップページ -- アルゴリズムとデータ構造編
この章の概要です。
関連する話題が、以下のページにあります。
この章では、二分探索（バイナリサーチ）というアルゴリズムを紹介します。
二分探索は非常に重要度の高いアルゴリズムです。このアルゴリズムの考え方は、探索に限らず、さまざまな場面で応用できるからです。
二分探索を使って探索を行うには、対象のデータの集まりがソート済みでなければならないという前提条件があります。
二分探索は、まず、データの集まりの中央にあたる場所を調べます。たとえば、対象のデータが、昇順にソートされた要素数 100個の配列だとすると（配列の名前は array とします）、array[49] を調べる訳です。中央の場所は (0 + 99) / 2 とすれば求められますから、これは問題ありません。もし、array[49] が目的の値そのものだったら、この時点で探索完了です。
さて、目的の値が 70 だとして、array[49] には 40 が格納されていたとしましょう。この場合、目的の値があるとすれば、array[50]～array[99] のどこかにあることが確定します。なぜなら、事前に昇順にソートされているからです。array[49] の値が 40 なら、70 は決してそれより手前にはありません。
そこで今度は、array[50]～array[99] の中央にあたる array[74] を調べます。これも (50 + 99) / 2 とすれば求められます。中央にあたる位置に目的の要素があればそれで完了ですし、なければ、それより手前か後ろを調べます。仮に、array[74] に 90 が格納されていたとすれば、array[50]～array[73] のどこかにあるだろうと考えられます。
このように、二分探索は、全体を半分を分けていく過程を繰り返していくのが基本的な流れです。たった１度の比較で、対象がどんどん半分に減っていくので、線形探索と比べて非常に高速に絞り込まれていきます。
しかし、二分探索には大きな問題が２つあります。
まず、対象のデータ構造が、各要素に直接アクセスできるものである必要があります。これは、「中央の位置」が一発で参照できなければ、性能が極端に低下するからです。この特性のため、連結リストからの探索には向いていません。
また、二分探索は、対象のデータ列がソートされていなければなりません。プログラムの実行開始前の時点でソート済みにしておけるならまったく問題ありませんが、常に変化し続けるデータ列を対象とする場合、ソートにかかる時間が無視できなくなるかもしれません。
昇順にソートされた配列を前提として、二分探索を実装してみます。
#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 };
int* p = binary_search( array, SIZE_OF_ARRAY(array), 7 );
if( p == NULL ){
puts( "見つかりませんでした。" );
}
else{
puts( "見つかりました。" );
}
return 0;
}
/*
二分探索
対象の配列array は昇順にソートされていることを前提としている。
*/
int* binary_search(int* array, size_t size, int value)
{
int lower = 0; // 探索範囲の下限の添字
int upper = 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;
}実行結果：
見つかりました。基本的には、冒頭の説明どおりの実装です。終了判定には触れていませんでしたが、目的の値が見つかったのなら、その時点で終了するだけです。目的の値が見つからなかったことを検出するには、探索範囲の上限と下限が逆転してしまったかどうかを調べます。
二分探索の実際の性能を確認しておきましょう。シンプルな線形探索と比較してみます。
#include <stdio.h>
#include "ppp_perform.h"
#define ARRAY_SIZE (1000)
#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)
{
int array[ARRAY_SIZE];
for( int i = 0; i < ARRAY_SIZE; ++i ){
array[i] = i;
}
PPP_CHECK_PERFORM_BEGIN(100000);
linear_search( array, SIZE_OF_ARRAY(array), 800 );
PPP_CHECK_PERFORM_END("linear_search");
PPP_CHECK_PERFORM_BEGIN(100000);
binary_search( array, SIZE_OF_ARRAY(array), 800 );
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 = 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;
}実行結果：
linear_search: 0.265000 seconds
binary_search: 0.008000 seconds0～999 の値が格納された要素数1000 の配列から、800 を探す操作を 100000回繰り返しています。実行結果のように、二分探索の方が圧倒的に高速になりました。
これだけ高速になるのは、線形探索だと 800回もの比較操作が必要ですが、二分探索なら 8回の比較で済んでしまうからです。二分探索は 1回の比較で、対象が半分に減ります。言い換えると、データ量が倍になっても、比較回数は 1回しか増えません。これは計算量で表すと O(log n) です。
さて、二分探索が常に線形探索より高速かというと、そういう訳ではありません。先ほどのサンプルプログラムで、探し出す値を 800 から 0 に変えて実行すると、次のような実行結果が得られます。
実行結果：
linear_search: 0.003000 seconds
binary_search: 0.008000 secondsわずかな差ではありますが、二分探索の方が遅くなりました。探す値が 0 の場合だと、線形探索なら最初の比較で発見できるため非常に高速になります。二分探索だと、中央にある要素を探して、探索範囲を狭めていくため、この場合 9回の比較が必要です。
二分探索は線形探索よりも、"常に速い" のではなく "平均的に速い" ということです。データ件数がある程度大きければ（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[%d])\n", p - array );
}
return 0;
}
/*
二分探索
対象の配列array は昇順にソートされていることを前提としている。
*/
int* binary_search(int* array, size_t size, int value)
{
int lower = 0; // 探索範囲の下限の添字
int upper = 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[%d])\n", p - array );
}
return 0;
}
/*
二分探索
対象の配列array は昇順にソートされていることを前提としている。
*/
int* binary_search(int* array, size_t size, int value)
{
int lower = 0; // 探索範囲の下限の添字
int upper = 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文が追加されたことです。ここで最終的に、探索の成否が確定します。
結局のところ何をしているかというと、目的の値と一致している間はループを終わらせず、一致する可能性が完全になくなる段階までループを続行しています。こうすると、目的の値が複数並んでいたとき、注目位置が少しずつ手前の方へ移動してきます。
分かりづらいですが、配列の中身をすべて同じ値にして、その値を探し出すようすると多少理解しやすいかもしれません。次のプログラムを試してみましょう。
#include <assert.h>
#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)
{
assert(size < INT_MAX);
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 「値が重複している場合」のサンプルプログラムの実行結果が間違っていたのを修正。
'2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。
≪さらに古い更新履歴を展開する≫
前の章へ （第３章 線形探索の効率改善②（自己組織化探索））
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| Twitter でツイート | Twitter をフォロー | LINE で送る |
|
RSS
|
管理者情報 | プライバシーポリシー |