二分探索

管理されたデータセットは、ほとんどの場合、整列されています。「整列されたデータ」は探索（検索）しやすいのです。

二分探索は、データの探索キーの大小関係を利用して、高速なデータ探索を可能にします。ここで重要なことは、「データが探索キーによって順番に整列されている」場合に限り、二分探索が適用できます。例えば、以下の「生徒名簿」について考えてみましょう。

学籍番号	名前	年齢	学科
1110171	Nuno	21	ソフト
1120085	Dai	21	ソフト
5101113	nobe	22	情報
8061103	fuku	26	情報システム
8071201	Sato	26	コンピュータ

この生徒名簿では、「学籍番号」を探索キーとすれば、二分探索が適用できます。なぜなら「学籍番号」が昇順に整列されているからです。しかし、例えば「名前」を探索キーとした場合は、二分探索が適用できません。

二分探索の原理はとても簡単です。データが1次元の配列に格納されているとします。

１. 最初はデータセット全体を探索の範囲とする
２. 探索の範囲中のまん中の要素を調べる
３. 目的の要素とまん中の要素が一致すれば終了
４. 目的の値が、まん中の値よりも小さければ前半部分を、大きければ後半部分を探索の範囲として２へ戻る

探索の範囲が半分になっていくので、高速な探索になります。

see-try-see

二分探索のプログラムです。

#include<iostream>
using namespace std;

#define MAX 10000
#define NOT_FOUND (-1)

int binarySearch( int data[], int size, int key ){
    int mid, left, right;
    left = 0; // 左端
    right = size; // 右端 + 1

    while ( left < right ){
        mid = ( left + right ) / 2; // 真ん中のインデックスを求める
        if ( data[mid] == key ) return mid; // 目的の値を発見
        else if ( key < data[mid] ) right = mid; // 前半部分へ
        else left = mid + 1; // 後半部分へ
    }

    return NOT_FOUND; // 目的の値がなかった
}

int main(void){
    int size, data[MAX], key;
  
    cin >> size;
    for ( int i = 0; i < size; i++ ) cin >> data[i];
    cin >> key;

    int result = binarySearch(data, size, key);

    if ( result == NOT_FOUND ) cout << "not found. " << endl;
    else cout << result << endl;

    return 0;
}

探索の範囲を指定する変数 left と right 、探索範囲の中央を指定する変数 mid を用意します。left は探索の左端のデータを指し示し、right は右端 + 1 のデータを指し示します。二分探索は最初データセット全体を探索の範囲とするので、left を 0 に、right をデータセットのサイズ size に設定します。

012 行目の while ループで、現時点の探索範囲のまん中のインデックス mid が指し示す値と key とを比較してチェックしていきます。もし、値が一致しているならば、mid を返します。mid が指し示す値が key よりも大きいならば、目的の値は mid よりも前半部分にある可能性がある（後半にはない）ので、right を mid とすることで探索範囲を前半部分に設定します。逆の場合は、left を mid + 1 とすることで後半部分に設定します。ループの繰り返し条件である left < right は、探索範囲がまだ存在することを示し、もし探索範囲がなくなってしまったら、key が発見できなかったとして-1を返します。

線形探索（２）

単純な線形探索よりも効率の良い線形探索のアルゴリズムを考えます。繰り返しになりますが、単純な線形探索のプログラムでは、

1. index < size: indexがデータの末尾を越えていないかのチェック
2. data[ index ] == key : indexが指すデータの中身が目的の値でないかのチェック

の２つをチェックしなければなりませんでした。これから考えるアルゴリズムでは、データに「番兵」と呼ばれる特別な値を設置することによって、比較演算の回数を半減させます。下図は整数のデータが格納された配列から与えられた値を探索している様子を示しています。



この例でも、要素数が１２個の配列の中から８を探していて、配列の先頭から順番に各要素が８であるかどうかをチェックしています。重要なポイントは、データの末尾に番兵として目的の値である８を追加していることです。番兵を設置することによってデータの中に目的の値が存在することが保障されるので、探索している範囲がデータ数を超えてしまわないかのチェックを行う必要がなくなります。目的のデータが見つかったときの index がデータのサイズを超えていた場合（index　が size と等しい場合）、それは番兵を示すので、データに目的の値が存在しなかったことを示します。番兵を用いた線形探索のプログラムの例を以下に示します。

#include<iostream>
using namespace std;

#define MAX 10000
#define NOT_FOUND (-1)

int linearSearch( int data[], int size, int key ){
    int index = -1; // data[0]から検索を開始するため
    data[ size ] = key; // 番兵をセットする 

    while ( data[ ++index ] != key ); // 探索する

    if ( index == size ) return NOT_FOUND; // 番兵が機能した場合 
    else return index; // 目的の値を発見した場合 
}

09 行目でデータの末尾に番兵である key を設置します。その結果、メインループでの比較処理はdata[ ++index ] != key の１つしかありません。番兵がいるのでメインループの while( data[ ++index ] != key ); は必ず終了することが保障されます。つまり、データの範囲を超えてチェックしていまうという危険な処理を"番兵"が阻止します。メインループが終了した時の index の値が、目的の値を指します。データが見つからなかった場合は、index が番兵にたどりついてしまった場合、すなわち index が size に達してしまった場合です。

線形探索（１）

線形探索は最も単純で効率の悪いアルゴリズムと言えます。このアルゴリズムは、データセットの先頭から順番にデータを調べていきます。下の図は、整数のデータが格納された配列から、「与えられた値」を探索している様子を示しています。この例では、要素数が１２個の配列の中から「８」という数字を、配列の先頭から順番に探しています。目的のデータが見つかったときに処理が終了します。 。

このアルゴリズムはデータがどのような順番で配置されていても、データセットの中に目的のデータがあれば、正確にその要素を取得することができます。線形探索を実装したプログラムの例を以下に示します。

#include<iostream>
using namespace std;

#define MAX 10000
#define NOT_FOUND (-1)

int linearSearch( int data[], int size, int key ){
    for ( int index = 0; index < size; index++ ){
        if ( data[ index ] == key ) return index;    
    }
    return NOT_FOUND; // 見つからなかった場合
}

int main(void){
    int size, data[MAX], key;
  
    cin >> size;
    for ( int i = 0; i < size; i++ ) cin >> data[i];
    cin >> key;

    int result = linearSearch(data, size, key);
    
    if ( result == NOT_FOUND ) cout << "not found. " << endl;
    else cout << result << endl;

    return 0;
}

プログラムは非常に単純で、for ループを用いて、データの先頭から末尾まで調べていき、目的のデータが発見された時点で、そのインデックスを結果として返しています。見つからなかった場合は、特別な値として-1を返します

少し効率がよくなる実装方法。

探索

たくさんのデータが蓄えられているデータセットの中から、目的のデータを探し出す方法を考えてみましょう。問題を単純にするために、配列から、ある要素を探し出すアルゴリズムを考えます。

Ｏ表記法

Ｏ表記法は、Big-Oh-Notation とも呼ばれ、O(g(n)) のように n を入力のサイズとした関数の集合で表します。O(g(n))　は計算量が g(n) の定数倍で抑えられることを意味します。つまり、この表記は問題の各入力サイズに対して、そのサイズの任意のインスタンスを解くために必要な"最大"の演算回数を見積もります。ここで、インスタンスとは問題の全ての入力値に具体的な値を設定したものを言います。問題が与えられるときには必ず入力の上限が定義されます。いくつか例を挙げます。

問題と解法の例	効率の例	意味
与えられたx個のデータを、Ａというアルゴリズムで整列する。xの最大値はnとする。	この問題に対するAの効率はO(n2)である。	Aは最悪でn2の計算ステップが必要である。
x個の交差点とy個の道から成る地図情報を基に、交差点aから交差点bまでの最短距離をBというアルゴリズムで求める。ｘの最大値はn、ｙの最大値はmである。	この問題に対するBの効率はO(mlogn)である。	Bは最悪で mlognの計算ステップが必要である。

このように、O( )の引数はある関数となります。また、O( n )を「オーダーがnである」と言います。では、アルゴリズムの評価に関する典型的な関数について、実際の入力値nとその計算量を以下の表で見てみましょう。ここでlogは2を底とする対数関数です。

n	logn	n	nlogn	n2	2n	n!
1	1	1	1	1	2	1
5	2	5	10	25	32	120
10	3	10	30	100	1024	3628800
20	4	20	80	400	1048576
50	5	50	250	2500
100	6	100	600	10000
1000	9	1000	9000	1000000
10000	13	10000	130000	100000000
100000	16	100000	1600000
1000000	19	1000000	19000000

どの関数がどれだけ効率が良いか、または悪いかを考えてみましょう。オーダーがO(logn)、O(n)、O(nlogn)のアルゴリズムは効率が良いと言えます。ｎが増加しても計算量はさほど増加しません。逆に、オーダーがO(2ⁿ)やO(n!)のアルゴリズムは、入力nが数十になっただけで、計算量が何千桁にも至ってしまいます。地球上最速のコンピュータを使っても、数百年かかってしまうであろう計算量です。これらの効率の悪いオーダーは、総当りなどの、素朴で力任せのアルゴリズムに良く見られます。そして初心者のプログラマがよくはまってしまいます。しかしながら、世の中には未解決の問題も多々あり、それらを解くことのできる最速のアルゴリズムのオーダーがO(2ⁿ)である場合もあります。 重要なことは、プログラムを実装する前に、入力の上限から自分のアルゴリズムの最悪計算ステップを評価することです。これは、学習するよりも、難しい問題にチャレンジし、失敗を繰り返すことによって経験することができます。

アルゴリズムを実装する前に、

現在のコンピュータは膨大な計算を一瞬でこなすことができますが、すべての問題を高速に解決できるわけではありません。もちろん限界があります。膨大な量のデータを高速に計算する優れたプログラムを書くためには、問題の性質を十分に考慮し効率の良いアルゴリズムを考える必要があります。

アルゴリズムの効率とは

与えられた問題を解くためのアルゴリズムを考えるとき、そのアルゴリズムの効率を評価する「ものさし」が必要になります。アルゴリズムを考えてプログラムを実装するときには、まずその効率を測り、そのアルゴリズムの効率が与えられた問題を解くのに十分かどうかを確認する必要があります。この過程を無視すると、実装されたプログラムは使い物にならなかった、という失敗をしてしまいます。

効率の良いアルゴリズムに求められるものは、処理するデータの数が増加しても計算ステップ数が爆発的に（指数的に）増加しないという性質です。つまり、入力値によっては計算ステップ数が爆発的に増加し、事実上処理がストップしてしまうようなプログラムは使い物になりません。例えば、あるアルゴリズムがデータを100個処理するのに1秒しかかからなくても、データを10000個に増やすと数時間もかかる場合があります。アルゴリズムを実装したときに100個の入力データでテストし満足する結果が得られたとしても、実際にそのプログラムを使う人は10000個のデータを処理する必要があるかもしれません。コンピュータの処理能力は日々進歩していますが、処理するデータの量や処理の複雑さも日々増しています。コンピュータの計算能力が余っていれば使ってしまいたくなるのが人情です。ですから、後々まで通用する効率の良いアルゴリズムを追求しなければなりません。

アルゴリズム主に以下の２つの計算量で評価されます。

時間計算量（time complexity）
プログラムの実行に必要な時間を評価します。

領域計算量（space complexity）
プログラムの実行に必要な記憶領域で評価します。

時間計算量がよく用いられますが、どちらの評価が重要ということはなく、これらのバランスを考えてアルゴリズムを考えることが重要です。この効率の概念を無視してしまったら、これから学ぶアルゴリズムの意義も半減してしまいます。

Ｏ表記法

アルゴリズムとは

アルゴリズムとは「算法」「演算手順」などと直訳することができますが、広い意味では、「あることを達成するための手順」のことです。日常生活の例をとっても、朝起きて→着替えて→朝食を食べて→歯を磨いて→自転車で学校へ行く、という一連の行動も一種のアルゴリズムと考えることができます。一般的にコンピュータの世界ではデータ処理、数値演算、シミュレーションなどの問題を解決するための考え方や手法の事をアルゴリズムと言います。

さらに厳密に言えば、アルゴリズムとは「明確に定義された有限個の規則の集まりであって、有限回適用することにより"問題"を解くもの」です。世の中に存在する問題に応じて、アルゴリズムは無限に存在します。

問題とアルゴリズムの例：

アルゴリズムとは何かを具体的な問題の例を通して考えてみます。

問題：１０人分の生徒の名前と身長が記録されたデータを読み込んで、その中で身長が高い順に３人の名前を出力して下さい。類題

このような単純で中途半端な問題にも以下のようにいくつか解法が考えられます。

アルゴリズム１

1. １０人の中から身長が一番高い人を探して名前を出力する。
2. １０人の中から（１）ですでに選ばれた人以外から身長が一番高い人を探して名前を出力する。
3. １０人の中から（１）（２）ですでに選ばれた人以外から身長が一番高い人を探して名前を出力する。

アルゴリズム２

1. データを身長が高い順に整列する
2. データの最初の３人の名前を順番に出力する。

もちろんこれらはプログラムとして実装できるアルゴリズムです。この例では、データを整列する計算効率を考えればアルゴリズム１の方が優れているます。一方もしデータを整列するためのアルゴリズムを簡単に書けるまたは信頼できるプログラムが使えるのであれば、アルゴリズム２の方がプログラムが分かり易く簡潔になりかつエラーを出さずに実装できるかもしれません。

このように、与えられた問題には様々な解法が存在します。その解法がアルゴリズムであって問題の定義や性質、さらにプログラムで使うデータ構造などに応じて考えなければなりません。以下の一般化した問題は、どのようなアルゴリズムで解けるかを考えてみると良いかもしれません。

n 個の整数が与えられ、その中で値が大きい順にm 個出力して下さい。ただしn < 1000000、m < 1000 とします。