【ITニュース解説】LeetCode #704. Binary Search

二分探索（Binary Search）は、ソート済みデータの中から特定の要素を探し出すための非常に効率的なアルゴリズムだ。システムエンジニアを目指す上で、大量のデータの中から素早く情報を検索する技術は必須であり、二分探索はその基本的な手法の一つとして広く活用されている。今回の記事では、この二分探索の仕組みと、その効率性を示す計算量について、実際のコードを交えながら解説する。

まず、二分探索がなぜ効率的であるかという点から説明しよう。例えば、1000個の数字が順番に並んだリストの中から特定の数字を探す場合を想像してみてほしい。もし「線形探索」と呼ばれる手法を用いるなら、先頭から一つずつ数字を調べていくことになる。最悪の場合、1000個すべてを調べなければ目的の数字が見つからない可能性もある。これに対し、二分探索は探索範囲を半分ずつ絞り込んでいくため、はるかに少ない手順で目的の数字を見つけ出すことができる。

この効率性は「計算量（Complexity）」という指標で表現される。二分探索の「時間計算量（Time Complexity）」はO(log n)であり、記事にもあるように、これは非常に優れた値を示す。O(log n)とは、データ数nが増加しても、検索にかかる時間がデータ数の対数（log）に比例してしか増えないことを意味する。例えば、データ数が2倍になったとしても、検索にかかる時間はごくわずかしか増加しない。具体的には、1000個のデータであれば最大で約10回、100万個のデータでも最大で約20回の比較で目的の要素を見つけ出すことが可能となる。これは、線形探索がデータ数に比例して検索回数が増えるO(n)であるのと比較すると、その差は歴然としている。

また、記事には「空間計算量（Space Complexity）」がO(1)であると示されている。空間計算量とは、アルゴリズムが実行される際に必要とするメモリの量を指す。O(1)は「定数空間」と呼ばれ、データ数nの大きさに関わらず、必要とするメモリの量が一定であることを意味する。これは、二分探索が追加の大きなメモリ領域を必要としない、非常に省メモリなアルゴリズムであるという利点を示している。

それでは、具体的な二分探索のアルゴリズムを、提供されたJavaコードを基に見ていこう。

Copy
1class Solution {
2    public int search(int[] nums, int target) {
3        int low = 0;
4        int high = nums.length -1;
5
6        while (low <= high) {
7            int mid = low + (high -low) / 2;
8            if (target == nums[mid]) 
9                return mid;
10            else if (target < nums[mid])
11                high = mid -1;
12            else
13                low = mid + 1;
14        }
15        return -1;
16    } 
17}

このコードは、searchというメソッドの中で二分探索を実装している。引数として、ソート済みの整数の配列numsと、探したい値であるtargetを受け取る。

まず、探索範囲を示す二つの変数lowとhighが初期化される。 lowは探索範囲の最も低いインデックス（配列の先頭、0）を指す。 highは探索範囲の最も高いインデックス（配列の末尾、nums.length - 1）を指す。 これらの変数が、探索範囲の両端を管理する。

次に、while (low <= high)というループが登場する。このループは、lowがhigh以下である限り、つまり探索範囲がまだ存在している限り、処理を繰り返すことを意味する。もしlowがhighを超えた場合、それは探索範囲が逆転し、目的の要素が見つからなかったことを意味するため、ループを終了する。

ループの中では、まずmidという変数が計算される。 int mid = low + (high - low) / 2; この式は、現在の探索範囲（lowからhighまで）のちょうど中央のインデックスを計算している。lowとhighを単純に足して2で割る(low + high) / 2という方法もあるが、low + highの値が非常に大きくなった場合に整数の最大値を超えてしまう「オーバーフロー」という問題を防ぐため、low + (high - low) / 2という書き方が推奨される。

midで中央のインデックスが計算されたら、そのインデックスにある配列の値nums[mid]と、探しているtargetを比較する。

1. if (target == nums[mid])： もしtargetが中央の値と完全に一致した場合、目的の要素が見つかったことになる。この場合、そのインデックスmidを返してメソッドを終了する。

2. else if (target < nums[mid])： もしtargetが中央の値よりも小さい場合、目的の要素は配列の左半分（lowからmid - 1の範囲）に存在するはずである。なぜなら、配列はソートされているからだ。そこで、highをmid - 1に更新し、探索範囲を左半分に絞り込む。

3. else： 上記いずれにも当てはまらない場合、つまりtargetが中央の値よりも大きい場合、目的の要素は配列の右半分（mid + 1からhighの範囲）に存在するはずである。そこで、lowをmid + 1に更新し、探索範囲を右半分に絞り込む。

このループを繰り返すことで、探索範囲は毎回半分になり、最終的には目的の要素が見つかるか、探索範囲がなくなるかのどちらかになる。

もしループが終了しても目的の要素が見つからなかった場合（つまり、lowがhighを超えてしまった場合）、メソッドはreturn -1;を実行する。これは、一般的な慣習として、指定されたtargetが配列nums内に存在しないことを示す値である。

二分探索は、そのシンプルさと高い効率性から、データベースのインデックス検索や、特定の値を範囲内で見つける場合など、多くの場面で利用される基本的なアルゴリズムだ。ソート済みのデータ構造を扱う際には、その強力な力を発揮するため、システムエンジニアを目指す上で必ず理解しておくべき重要な概念である。このアルゴリズムを理解し、実装できることは、効率的なプログラム設計能力を高める上で非常に役立つだろう。