今回のテーマは「線形探索と二分探索」です。

線形探索は、リストの先頭から順に目的の値と一致するか判定していく探索アルゴリズムです。 どんなリストに対しても適用できますが、あまり効率的とは言えません。 二分探索は、目的の値が探索するリストの中央の値より大きいか小さいかを判断して次の探索範囲を絞りこみ、それを繰り返すことで目的の値を探索するアルゴリズムです。 例えば、{1,2,3,4,5,6,7,8}という値を持つリストから8という値を探す場合、最初の判定で探索範囲が{5,6,7,8}に絞られ、次の判定で{7,8}に絞られるといった感じです。 リストのサイズが大きいほど線形探索より探索効率は非常に良くなりますが、二分探索を適用するためにはリストがソート済みでなければなりません。

それではサンプルで線形探索と二分探索の速度比較を行ってみましょう。 二分探索はArraysクラスやCollectionsクラスでbinarySearchメソッドとして実装されています。

import java.util.Arrays; 
import java.util.Collections;

import org.apache.commons.lang.time.StopWatch;
public class Main { 
    public static void main(String[] args) { 
        // 探索する値の配列 
        String[] array1 = new String[15000]; 
        for (int i = 0; i < array1.length; i++) { 
            array1[i] = String.valueOf(i); 
        }

        // 探索される配列 
        String[] array2 = new String[10000]; 
        for (int i = 0; i < array2.length; i++) { 
            array2[i] = String.valueOf(i); 
        } 
        Collections.shuffle(Arrays.asList(array2));

        StopWatch stopWatch = new StopWatch(); 
        stopWatch.reset(); 
        stopWatch.start(); 
        for (int i = 0; i < array1.length; i++) { 
            linearSearch(array2, array1[i]); 
        } 
        stopWatch.stop(); 
        System.out.println("線形探索の場合：" + stopWatch.getTime() + "ミリ秒");

        stopWatch.reset(); 
        stopWatch.start(); 
        Arrays.sort(array2); 
        for (int i = 0; i < array1.length; i++) { 
            Arrays.binarySearch(array2, array1[i]); 
        } 
        stopWatch.stop(); 
        System.out.println("二分探索の場合：" + stopWatch.getTime() + "ミリ秒"); 
    }

    public static int linearSearch(Object[] array, Object key) { 
        for (int i = 0; i < array.length; i++) { 
            if (key.equals(array[i])) { 
                return i; 
            } 
        } 
        return -1; 
    } 
}

探索するリストが大きい場合、事前に配列のソート処理が必要だとしても、圧倒的に二分探索が速いですね。