このページではデータの探索及び、データ探索アルゴリズムの線形探索（リニアサーチ）・二分探索（バイナリサーチ）の解説と、そのプログラム例の紹介を行なっていきたいと思います。
Contents
データの探索
探索とは「ある特定の条件を満たす物を見つけ出すこと」であり、特にデータの探索とは、集合の中から探索したいデータを見つけ出すことになります。
例えば下図のような会員データの中かから、
会員番号が「２５６」のデータを見つけ出したり、
名前が「KEI」のデータを見つけ出したりします。
こんな感じで特定の項目（上記の例だと会員番号や名前）が特定の値（上位の例だと「２５６」や「KEI」）であるデータを見つけ出すのがデータ探索になります。
ではどうやってデータを見つけ出すのか？
この見つけ出す手順が「探索アルゴリズム」になります。
この探索アルゴリズムには様々なものが存在します。
このページでは、このデータの探索のアルゴリズムの中で最も単純な下記の２つのアルゴリズムについて解説していきたいと思います。
- 線形探索
- 二分探索
線形探索
まずは線形探索について解説していきます。線形探索は「リニアサーチ」と呼ばれることもあります。最も簡単な探索アルゴリズムだと思います。
スポンサーリンク
線形探索の考え方
線形探索は、探索しているデータかどうかをデータの集合（配列やリストなど）の先頭から順に１つ１つ調べる方法になります。
例えば下のようなデータの集合から「１５」を探索することを考えます。
まず調べるのはデータの集合の先頭のデータです。このデータが「１５」であるかどうかを調べます。
先頭のデータは「１５」ではないので、次のデータが「１５」であるかどうかを調べます。
これも「１５」ではありませんので、今度はさらに次のデータを調べます。
こんな感じでデータの先頭から順にデータを探索したいデータと一致するかどうかを１つ１つ比較して調べていくのが「線形探索」です。
データが探索したいデータと一致した場合は、その時点で探索を終了します。
最後のデータまで調べてもデータが見つからない場合は、データの集合の中には探索したいデータが無いということになります。
線形探索のプログラム例（数字の探索）
下記がC言語で線形探索（数字の探索）を実装した例となります。
initArray で構造体の配列にランダムに数字を格納することでデータの集合を生成し、linearSearchByNumber 関数で NUM - 1 （NUM は 100000 で定義）の値の探索を行なっています。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
/* データの数 */
#define NUM 100000
/* 名前の最大文字数 */
#define NAME_MAX 8
typedef struct {
int number;
char name[NAME_MAX];
} DATA_T;
/* 線形探索（リニアサーチ）を行う関数
* data[] : サーチを行うデータの集合
* number : サーチする番号
* num_data : data[] のデータ数
*/
int linearSearchByNumber(DATA_T data[], int number, int num_data) {
int i;
for (i = 0; i < num_data; i++) {
/* 文字列を先頭から順に１つずつ比較 */
if (data[i].number == number) {
/* 一致したら探索終了 */
return i;
}
}
/* 見つからなかった場合 */
return -1;
}
/* 配列を初期化する関数 */
void initArray(DATA_T a[], int data_num) {
int i;
int c;
int num_name;
int num_alphabet;
/* numberを乱数で初期化 */
for (i = 0; i < data_num; i++) {
a[i].number = rand() % data_num;
}
/* アルファベットの数を計算 */
num_alphabet = 'Z' - 'A' + 1;
/* nameを乱数で初期化 */
for (i = 0; i < data_num; i++) {
/* 名前の文字数を(1 から NAME_MAX - 1)の間でランダムに決定 */
num_name = (rand() % (NAME_MAX - 1)) + 1;
/* 文字数分の文字を格納 */
for (c = 0; c < num_name; c++) {
a[i].name[c] = (rand() % num_alphabet) + 'A';
}
/* 最後にヌル文字を格納 */
a[i].name[c] = '\0';
}
}
int main(void) {
DATA_T data[NUM];
int number;
char name[NAME_MAX];
int num_data;
int ret;
clock_t start, end;
/* 現在時刻の情報で初期化 */
srand((unsigned int)time(NULL));
/* データ数を設定 */
num_data = NUM;
/* 探索する数字を設定 */
number = NUM - 1;
/* 配列を初期化 */
initArray(data, num_data);
printf("%dを探索\n", number);
start = clock();
/* 線形探索 */
ret = linearSearchByNumber(data, number, num_data);
end = clock();
/* 処理結果を表示 */
if (ret == -1) {
printf("データが見つかりませんでした\n");
} else {
printf("data[%d].number = %d\n", ret, data[ret].number);
}
printf("処理時間：%f\n", (double)(end - start) / CLOCKS_PER_SEC);
return 0;
}実行すると探索結果が表示されます。
私が実際に実行した時の結果は下記のようになりました（データの集合をランダムに生成しているので見つからない場合もあります）。
99999を探索 data[45677].number = 99999 処理時間：0.000176
線形探索のプログラム例（文字列の探索）
下記がC言語で線形探索（文字列の探索）を実装した例となります。
initArray で構造体の配列にランダムに文字列を格納することでデータの集合を生成し、linearSearchByName 関数で TARO の文字列の探索を行なっています。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <string.h>
/* データの数 */
#define NUM 100000
/* 名前の最大文字数 */
#define NAME_MAX 8
typedef struct {
int number;
char name[NAME_MAX];
} DATA_T;
/* 線形探索（リニアサーチ）を行う関数
* data[] : サーチを行うデータの集合
* name : サーチする文字列
* num_data : data[] のデータ数
*/
int linearSearchByName(DATA_T data[], char *name, int num_data) {
int i;
for (i = 0; i < num_data; i++) {
/* 文字列を先頭から順に１つずつ比較 */
if (!strcmp(data[i].name, name)) {
/* 一致したら探索終了 */
return i;
}
}
/* 見つからなかった場合 */
return -1;
}
/* 配列を初期化する関数 */
void initArray(DATA_T a[], int data_num) {
int i;
int c;
int num_name;
int num_alphabet;
/* numberを乱数で初期化 */
for (i = 0; i < data_num; i++) {
a[i].number = rand() % data_num;
}
/* アルファベットの数を計算 */
num_alphabet = 'Z' - 'A' + 1;
/* nameを乱数で初期化 */
for (i = 0; i < data_num; i++) {
/* 名前の文字数を(1 から NAME_MAX - 1)の間でランダムに決定 */
num_name = (rand() % (NAME_MAX - 1)) + 1;
/* 文字数分の文字を格納 */
for (c = 0; c < num_name; c++) {
a[i].name[c] = (rand() % num_alphabet) + 'A';
}
/* 最後にヌル文字を格納 */
a[i].name[c] = '\0';
}
}
int main(void) {
DATA_T data[NUM];
int number;
char name[NAME_MAX];
int num_data;
int ret;
clock_t start, end;
/* 現在時刻の情報で初期化 */
srand((unsigned int)time(NULL));
/* データ数を設定 */
num_data = NUM;
/* 配列を初期化 */
initArray(data, num_data);
/* 探索する文字列を設定 */
strcpy(name, "TARO");
printf("%sを探索\n", name);
start = clock();
/* 線形探索 */
ret = linearSearchByName(data, name, num_data);
end = clock();
/* 処理結果を表示 */
if (ret == -1) {
printf("データが見つかりませんでした\n");
} else {
printf("data[%d].name = %s\n", ret, data[ret].name);
}
printf("処理時間：%f\n", (double)(end - start) / CLOCKS_PER_SEC);
return 0;
}こちらも実行すると探索結果が表示されます。
私が実際に実行した時の結果は下記のようになりました（データの集合をランダムに生成しているので見つからない場合もあります）。
TAROを探索 data[63451].name = TARO 処理時間：0.000513
スポンサーリンク
二分探索
続いて二分探索について解説していきます。二分探索は「バイナリサーチ」とも呼ばれます。
この「二分する」考え方は様々なアルゴリズムで出てきますのでしっかり覚えておきましょう！
二分探索の考え方
二分探索は、データの集合を二分（半分に）しながらデータの探索範囲を狭めていく探索アルゴリズムです。
この二分探索を行うためには「データの集合が昇順 or 降順に整列されている（ソートされている）こと」という制約があります。
今後の解説はデータの集合が「昇順」に整列されていることとして解説していきます
データの集合が「降順」に整列されている場合の二分探索については大小関係等を逆に解釈してください
データの集合が整列されているので、下記のようにデータの探索を行うことができます。この方法で探索を行うのが二分探索になります。
- 探索したいデータとデータの集合の中央のデータの大小関係を調べる（☆）
- 一致する場合：
- 探索したいデータが見つかったので探索を終了する
- 探索したいデータの方が小さい場合：
- データの集合の中央よりも「前方のデータのみを新たなデータの集合」として☆に戻る
- 探索したいデータの方が大きい場合：
- データの集合の中央よりも「後方のデータのみを新たなデータの集合」として☆に戻る
- 一致する場合：
例えば下のような昇順に整列済みのデータの集合から「７」を探索することを考えます。
まずは探索したいデータとデータの集合の中央の位置にあるデータとの大小関係を調べます（データ数が偶数の倍は中央が２つありますが、この場合はどちらを調べても良いです）。
探索したいデータの方が小さいですね。ここでデータの集合が昇順に整列されていることを思い出してください。
データの集合が昇順に整列されているので、中央の位置よりも後方のデータは全て中央の位置のデータ以上のデータになります。
したがって、「探索したいデータ」が「中央の位置のデータ」よりも小さいのであれば、中央の位置から後方には探索したいデータは存在しないことになります。
なので、次は中央の位置から後方のデータは探索範囲から外して、つまり中央の位置よりも前方のデータのみを新しいデータの集合として再度二分探索を行なっていきます。
続いて、「探索したいデータ」と「新たなデータの集合の中央のデータ」の大小関係を調べます。
探索したいデータの方が大きいので、今度はデータの集合の中央の位置よりも後方のみを新たなデータの集合として二分探索を行なっていきます。
今度は探索したいデータと新たなデータ集合の中央の値の大小関係を比較すると、値が一致するためデータが見つかったことになり、この時点で探索を終了します。
こんな感じで探索したいデータと中央のデータの大小関係からどんどん探索範囲を狭めながら探索を行うのが二分探索になります。
探索範囲が１つ未満になっても探索したいデータが見つからない場合は、探索したいデータはデータの集合の中に存在しないことになります。
ここまで解説してきたように二分探索は「データが整列されている」ことを前提としてデータの集合を二分しながらデータの探索を行うアルゴリズムになります。
したがって整列されていないデータに対しては二分探索を行うことはできません。
もし整列されていないデータに二分探索を行う際には、事前にデータの集合の整列（ソート）を行う必要があります。
二分探索のプログラム例（数字の探索）
下記がC言語で二分探索（数字の探索）を実装した例となります。
initArray で構造体の配列にランダムに数字を格納することでデータの集合を生成し、BinarySearchByNumber 関数で NUM - 1 （NUM は 100000 で定義）の値の探索を行なっています。
二分探索（BinarySearchByNumber）を行う前に、main 関数で事前にクイックソート関数（quickSortByNumber）を呼び出しています。
クイックソートに関しては下記ページで解説していますので、プログラムで何をやっているかがわからない方やソートに興味のある方はぜひ読んでみてください。
クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
/* データの数 */
#define NUM 100000
/* 名前の最大文字数 */
#define NAME_MAX 8
typedef struct {
int number;
char name[NAME_MAX];
} DATA_T;
/* データを入れ替える関数 */
void swap(DATA_T *a, DATA_T *b) {
DATA_T tmp;
tmp = *b;
*b = *a;
*a = tmp;
}
/* クイックソートを行う関数 */
void quickSortByNumber(DATA_T a[], int left, int right) {
int pivot;
int i, j;
/* ソートを行う範囲が１以下の場合 */
if(left >= right) {
return;
}
/* pivot の決定 */
pivot = a[left].number;
/* 探索範囲の初期化 */
i = left;
j = right;
/* pivot以下の数字を配列の前半に
pivot以上の数字を配列の後半に集める */
while(1) {
/* pivot以上の数字を左側から探索 */
while (a[i].number < pivot) {
i++;
}
/* pivot以下の数字を左側から探索 */
while (a[j].number > pivot) {
j--;
}
/* i >= j になったということは
配列の左側にpivot以下の数字が、
配列の右側にpivot以上の数字が集まったということ */
if (i >= j) {
/* 集合の分割処理は終了 */
break;
}
/* 探索した２つのデータを交換 */
swap(&(a[i]), &(a[j]));
/* 交換後の数字の次から探索再開 */
i++;
j--;
}
/* 小さい数字を集めた範囲に対してソート */
quickSortByNumber(a, left, i - 1);
/* 大きい数字を集めた範囲に対してソート */
quickSortByNumber(a, j + 1, right);
}
/* 二分探索（バイナリサーチ）を行う関数
* data[] : サーチを行うデータの集合
* number : サーチする番号
* left : 探索する範囲の左端
* right : 探索する範囲の右端
*/
int BinarySearchByNumber(DATA_T data[], int number, int left, int right) {
int mid;
int ret;
if (right < left) {
/* 探索する範囲が0になったら終了 */
return -1;
}
/* データの集合の中央の位置を計算 */
mid = left + (right - left) / 2;
/* 探索したい数字と集合の中央の位置の数字の差を計算 */
ret = number - data[mid].number;
if (ret == 0) {
/* 差がない場合は中央の位置が探索したいデータ */
return mid;
}
if (ret > 0) {
/* 差が１以上の場合は中央より後方を新しい集合として再度探索 */
ret = BinarySearchByNumber(data, number, mid + 1, right);
} else {
/* 差がー１以下の場合は中央より前方を新しい集合として再度探索 */
ret = BinarySearchByNumber(data, number, left, mid - 1);
}
return ret;
}
/* 配列を初期化する関数 */
void initArray(DATA_T a[], int data_num) {
int i;
int c;
int num_name;
int num_alphabet;
/* numberを乱数で初期化 */
for (i = 0; i < data_num; i++) {
a[i].number = rand() % data_num;
}
/* アルファベットの数を計算 */
num_alphabet = 'Z' - 'A' + 1;
/* nameを乱数で初期化 */
for (i = 0; i < data_num; i++) {
/* 名前の文字数を(1 から NAME_MAX - 1)の間でランダムに決定 */
num_name = (rand() % (NAME_MAX - 1)) + 1;
/* 文字数分の文字を格納 */
for (c = 0; c < num_name; c++) {
a[i].name[c] = (rand() % num_alphabet) + 'A';
}
/* 最後にヌル文字を格納 */
a[i].name[c] = '\0';
}
}
int main(void) {
DATA_T data[NUM];
int number;
char name[NAME_MAX];
int num_data;
int ret;
clock_t start, end, processing;
/* 現在時刻の情報で初期化 */
srand((unsigned int)time(NULL));
/* データ数を設定 */
num_data = NUM;
/* 配列を初期化 */
initArray(data, num_data);
/* クイックソートでデータを整列 */
quickSortByNumber(data, 0, num_data - 1);
/* 探索する数字を設定 */
number = NUM - 1;
printf("%dを探索\n", number);
start = clock();
/* 二分探索 */
ret = BinarySearchByNumber(data, number, 0, num_data - 1);
end = clock();
/* 処理結果を表示 */
if (ret == -1) {
printf("データが見つかりませんでした\n");
} else {
printf("data[%d].number = %d\n", ret, data[ret].number);
}
printf("処理時間：%f\n", (double)(end - start) / CLOCKS_PER_SEC);
return 0;
}実行すると探索結果が表示されます。
私が実際に実行した時の結果は下記のようになりました（データの集合をランダムに生成しているので見つからない場合もあります）。
99999を探索 data[99999].number = 99999 処理時間：0.000003
線形探索に比較して処理時間が短いことが確認できると思います。
スポンサーリンク
二分探索のプログラム例（文字列の探索）
下記がC言語で二分探索（文字列の探索）を実装した例となります。
initArray で構造体の配列にランダムに文字列を格納することでデータの集合を生成し、BinarySearchByName 関数で TARO の文字列の探索を行なっています。
二分探索（BinarySearchByName）を行う前に、main 関数で事前にクイックソート関数（quickSortByName）を呼び出しています。
文字列の大小関係は strcmp 関数により実行しています。
strcmp 関数は引数で指定した２つの文字列が同じであるかだけでなく、どちらの文字列が文字コードとして大きいか小さいかも引数で教えてくれる関数になります。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <string.h>
/* データの数 */
#define NUM 100000
/* 名前の最大文字数 */
#define NAME_MAX 8
typedef struct {
int number;
char name[NAME_MAX];
} DATA_T;
/* データを入れ替える関数 */
void swap(DATA_T *a, DATA_T *b) {
DATA_T tmp;
tmp = *b;
*b = *a;
*a = tmp;
}
/* クイックソートを行う関数 */
void quickSortByName(DATA_T a[], int left, int right) {
char pivot[NAME_MAX];
int i, j;
/* ソートを行う範囲が１以下の場合 */
if(left >= right) {
return;
}
/* pivot の決定 */
strcpy(pivot, a[left].name);
/* 探索範囲の初期化 */
i = left;
j = right;
/* pivot以下の数字を配列の前半に
pivot以上の数字を配列の後半に集める */
while(1) {
/* pivot以上の数字を左側から探索 */
while (strcmp(a[i].name, pivot) < 0) {
i++;
}
/* pivot以下の数字を左側から探索 */
while (strcmp(a[j].name, pivot) > 0) {
j--;
}
/* i >= j になったということは
配列の左側にpivot以下の数字が、
配列の右側にpivot以上の数字が集まったということ */
if (i >= j) {
/* 集合の分割処理は終了 */
break;
}
/* 探索した２つのデータを交換 */
swap(&(a[i]), &(a[j]));
/* 交換後の数字の次から探索再開 */
i++;
j--;
}
/* 小さい数字を集めた範囲に対してソート */
quickSortByName(a, left, i - 1);
/* 大きい数字を集めた範囲に対してソート */
quickSortByName(a, j + 1, right);
}
/* 二分探索（バイナリサーチ）を行う関数
* data[] : サーチを行うデータの集合
* name : サーチする文字列
* left : 探索する範囲の左端
* right : 探索する範囲の右端
*/
int BinarySearchByName(DATA_T data[], char *name, int left, int right) {
int mid;
int ret;
if (right < left) {
/* 探索する範囲が0になったら終了 */
return -1;
}
/* データの集合の中央の位置を計算 */
mid = left + (right - left) / 2;
/* 探索したい文字列と集合の中央の位置の文字列を比較 */
ret = strcmp(name, data[mid].name);
if (ret == 0) {
/* 一致した場合は中央の位置が探索したいデータ */
return mid;
}
if (ret > 0) {
/* strcmpが１以上の場合は中央より後方を新しい集合として再度探索 */
ret = BinarySearchByName(data, name, mid + 1, right);
} else {
/* strcmpが−１以下の場合は中央より前方を新しい集合として再度探索 */
ret = BinarySearchByName(data, name, left, mid - 1);
}
return ret;
}
/* 配列を初期化する関数 */
void initArray(DATA_T a[], int data_num) {
int i;
int c;
int num_name;
int num_alphabet;
/* numberを乱数で初期化 */
for (i = 0; i < data_num; i++) {
a[i].number = rand() % data_num;
}
/* アルファベットの数を計算 */
num_alphabet = 'Z' - 'A' + 1;
/* nameを乱数で初期化 */
for (i = 0; i < data_num; i++) {
/* 名前の文字数を(1 から NAME_MAX - 1)の間でランダムに決定 */
num_name = (rand() % (NAME_MAX - 1)) + 1;
/* 文字数分の文字を格納 */
for (c = 0; c < num_name; c++) {
a[i].name[c] = (rand() % num_alphabet) + 'A';
}
/* 最後にヌル文字を格納 */
a[i].name[c] = '\0';
}
}
int main(void) {
DATA_T data[NUM];
int number;
char name[NAME_MAX];
int num_data;
int ret;
clock_t start, end;
/* 現在時刻の情報で初期化 */
srand((unsigned int)time(NULL));
/* データ数を設定 */
num_data = NUM;
/* 配列を初期化 */
initArray(data, num_data);
/* クイックソートでデータを整列 */
quickSortByName(data, 0, num_data - 1);
/* 探索する文字列を設定 */
strcpy(name, "TARO");
printf("%sを探索\n", name);
start = clock();
/* 二分探索 */
ret = BinarySearchByName(data, name, 0, num_data - 1);
end = clock();
/* 処理結果を表示 */
if (ret == -1) {
printf("データが見つかりませんでした\n");
} else {
printf("data[%d].name = %s\n", ret, data[ret].name);
}
printf("処理時間：%f\n", (double)(end - start) / CLOCKS_PER_SEC);
return 0;
}こちらも実行すると探索結果が表示されます。
私が実際に実行した時の結果は下記のようになりました（データの集合をランダムに生成しているので見つからない場合もあります）。
TAROを探索 data[73988].name = TARO 処理時間：0.000013/pre>
文字列の探索においても線形探索に比較して処理時間が短いことが確認できると思います。
線形探索と二分探索の比較
ここからはここまで解説してきた線形探索と二分探索の比較を行っていきたいと思います。
アルゴリズムの制約
アルゴリズムが適用できる条件・制約について比較を行いたいと思います。
線形探索の制約
線形探索では特に制約はありません。どんなデータの集合にも適用できます。
二分探索の制約
一方、二分探索では下記の制約があります。
- データが整列（ソート）されている必要がある
- そもそも整列できないようなデータの集合には適用できない
スポンサーリンク
演算量の比較
次は演算量の比較を行っていきたいと思います
線形探索の演算量
線形探索では、集合内のデータの数を N とした時、線形探索における演算量（比較回数）のオーダーは O(N) となります。つまり、データ数に比例して比較回数が増加していくことになります。
最悪のケース（探索したいデータが無い、探索したいデータがデータの集合の末尾にある）では比較回数が N 回となり、平均比較回数は （N + 1） / 2 となります。
例えばデータ数が１６で、探索したいデータが集合の末尾にある場合は、探索が完了するまでに必要な比較回数は１６回となります。
二分探索の演算量
集合内のデータの数を N とした時、二分探索における演算量（比較回数）のオーダーは O(logN) となります（log の底は２）。
要はデータの集合が１つになるまで二分できる回数に比例して演算量が増加していくということになります（下記はデータ数が１６の集合が４回二分 [log16 = 4] できる様子）。
最悪のケース（探索したいデータが無い、探索したいデータがデータの集合の末尾にある）では比較回数が logN ＋１回となり、平均比較回数は logN となります。
例えばデータ数が１６で、探索したいデータが集合の末尾にある場合は、探索が完了するまでに必要な比較回数は５回（log16 + 1）となります。
例えばデータ数が 65536 個の場合、各アルゴリズムにおける最悪演算量は下記のようになります。
- 線形探索：65536 回
- 二分探索：17 回
こんな感じでデータ数が多ければ多いほど、線形探索と二分探索との演算量（特に平均比較回数・最悪平均比較回数）の差が大きくなります。
メリットとデメリット
最後に線形探索と二分探索をそれぞれ比較したメリットとデメリットをまとめておきます。
線形探索のメリット・デメリット
二分探索と比較した際の、線形探索のメリットとデメリットは下記のようになります。
- メリット
- アルゴリズムが簡単（実装も簡単）
- 使用できるデータの集合に制約がない
- デメリット
- 平均演算回数・最悪演算回数が多い（つまり探索が遅い）
二分探索のメリット・デメリット
線形探索と比較した際の、二分探索のメリットとデメリットは下記のようになります。
- メリット
- 平均演算回数・最悪演算回数が少ない（つまり探索が速い）
- デメリット
-
- 若干アルゴリズムが複雑
- データの集合は昇順 or 降順に整列されている必要がある（適用できるデータの集合に制約がある）
-
二分探索を有効利用する方法
ここまで解説してきたように、探索自体は線形探索よりも二分探索の方が基本的に高速です。
ただし、二分探索では前述のように事前にデータをソートしておく必要があり、このデータのソートは探索に比較して処理が非常に遅いです。
例えば、二分探索のプログラム例（数字の探索）で示したプログラムでソートを行うために要した処理時間を表示すると下記のようになりました。
ソート時間：0.021379
99999を探索
data[99999].number = 99999
処理時間：0.000003
探索に要した処理時間に比較して非常に遅いことが確認できると思います。
線形探索のプログラム例（数字の探索）で示した処理時間に比べても遅いです。
つまり、二分探索の前にソートを行うことを考えると、実は線形探索の方が二分探索よりも高速です。
スポンサーリンク
データ構造を工夫して二分探索を有効利用
ただし、何度も言っているように二分探索は探索自体は線形探索よりも高速です。
この二分探索の探索速度の速さを最大限に発揮するためには下記を行うことが有効です。
- データを常に整列した状態にしておく
例えばデータが追加された際に集合の末尾にデータを追加するのではなく、データの整列が保たれた状態になるように追加すれば、二分探索時実行時に事前にわざわざソート処理を行う必要がなく、常に高速に探索を行うことができます。
また、二分木というデータ構造を利用すれば、常にデータの整列が保たれた状態でデータの追加や削除が可能になります。
こんな感じで、探索方法に合わせてデータ構造を工夫することで、二分探索の効果を最大限に発揮することができます。
ただし、整列した状態でデータを追加するためには、データの追加に必要な時間が増加してしまうことになります。
データの追加とデータの探索のどちらを高速に処理を行いたいかをアプリやシステムのユースケースの特性から考え、適切にデータ構造とアルゴリズムを選択することが重要です。
まとめ
このページでは基本的な探索アルゴリズムである「線形探索」と「二分探索」について解説を行いました。
これらのアルゴリズム自体は比較的簡単なので、アルゴリズムの入門としては最適なテーマだと思います。
アルゴリズム自体（どのように処理が行われるか）のみだけでなく、アルゴリズムを比較することも重要ですので、この際に一緒に学んでいただければと思います。
特に二分探索に関しては、探索の直前にデータのソートを行うと逆に線形探索よりも遅くなってしまいますので、常にデータが整列された状態で保つなど、データ構造に関しても一緒に考えてシステム全体の最適化を図りましょう！
