探索アルゴリズム (2)

前回に引き続き、今回もリスト探索のアルゴリズム 2分探索 を紹介します。
このアルゴリズムではリスト内から探索対象を探すのに O(log n) の計算量しかかかりません。

ただし、前提条件として、リストがランダムアクセス可能で、かつソート済である必要があります。

アルゴリズムの内容は至って単純で、探索対象とリストの探索範囲の中央にある要素を比較します。このとき

•一致していればその位置が結果となります。
•もし中央の要素が探索対象より大きければ、探索対象は探索範囲の中央より下側に含まれている可能性があるので、探索範囲の上限を中央より一つ下にして探索を続けます。
•そうでなく、もし中央の要素が探索対象より小ければ、探索対象は探索範囲の中央より上側に含まれている可能性があるので、探索範囲の下限を中央より一つ上にして探索を続けます。
探索範囲の下限が上限より大きくなった場合、これはつまり要素が見つからなかったということになります。

以下は Java のサンプルコードです。

search/list/BinarySearch.java

package search.list;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class BinarySearch {

    public static > int search(List list,
            T target) {
        return search(list, target, new DefaultComparator());
    }

    public static  int search(List list, T target,
            Comparator comparator) {
        return searchRecursive(list, target, comparator, 0, list.size());
    }

    public static  int searchRecursive(List list, T target,
            Comparator comparator, int start, int last) {
        if (start > last) {
            return -1;  // not found
        }
        int half = (start + last) / 2;
        int comp = comparator.compare(target, list.get(half)); 
        if (comp < 0) {
            /*
             *        It may be contained in this range.
             *                 <-------->
             * [X][X][X]...[X][X][X]...[X][X][X]...[X][X][X]...[X][X]
             *                 ^           ^           ^
             *               start        half        last
             */
            return searchRecursive(list, target, comparator, start, half);
        } else if (comp > 0) {
            /*
             *                       It may be contained in this range.
             *                                <----->
             * [X][X][X]...[X][X][X]...[X][X][X]...[X][X][X]...[X][X]
             *                 ^           ^           ^
             *               start        half        last
             */
            return searchRecursive(list, target, comparator, half + 1, last);
        } else {  // comp == 0
            return half;  // found
        }
    }

    public static void main(String... args) {
        final int MAX = 100;
        List list = new ArrayList();
        while (list.size() < MAX) {
            list.add((int) (Math.random() * Integer.MAX_VALUE));
        }
        Integer sample = list.get((int) Math.random() * list.size());
        Collections.sort(list);

        System.out.println("Look for `" + sample + "'");
        System.out.println("in the list " + list);


        int result = search(list, sample);
        assert (result >= 0);
        assert (sample.equals(list.get(result)));


        System.out.println("Result index: " + result);
    }

    private static class DefaultComparator>
            implements Comparator {

        @Override
        public int compare(T a, T b) {
            return a.compareTo(b);
        }
    }
}

2010年4月21日 | カテゴリー：アルゴリズム