プログラミング高速化ー二分探索について

こんには、ゴン権太丸です。

今日は2分探索の有効な使いどころが分かった気がしたので記事を書いていきたいと思います。

・配列へのアクセス方法について

配列の要素に一致する値を見つけるためにforで1つずつ値を比較しているとコード量も多くなるし、計算量も増えてしまいます。

下記の例だと19の要素を調べるのに配列の要素を10回かかってしまいます。

配列での探索

上記の場合のC#でのコードは下記になります

var list = new List{ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 };
int target;
for(int i = 0; i < list.Count(); i++)
{
    if (list[i] == 19)
    　　　target = i;
}

・２分探索

2分探索だと配列の真ん中の要素より対象が小さいか大きいかを比較してを繰り返して行います。比較する毎に探索範囲を狭めていく手法ですね。(計算量が大幅に削減できます。)

2分探索

C#でのコードは下記です。

var list = new List{ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 };
var result = list.BinarySearch(19);
if (result < 0)
    // 一致する要素が存在しない場合
    result = ~result;

 10回かかっていた計算が3回で済むようになりました…コードもすっきりしてる(感激) 

リストの要素が増えると計算量の削減幅も大幅に増えますね。

※ソートしてないリストだと意味わからん事になるので注意！！

BinarySearchの使い方の注意としては下記です。

・リストの中の要素がソートしていないと意味分からん値が返ってくる。

・リストに一致する値が存在しない場合、負の値で対象の次に大きい値の添え字のビット毎の補数が戻り値となる。(ビット反転させると対象の値の次に大きい要素の添え字になります。)

BinarySearchが使用できない言語でも自分で実装することで高速化が望めますよ～～

みなさんぜひぜひ！！