探索アルゴリズム (1)

そろそろソートアルゴリズムもネタが尽きてきましたので、探索アルゴリズムを紹介します。
まずはリスト探索アルゴリズムの線形探索を紹介します。

リストからオブジェクトを見つけるときにまず思いつくのは、リストの最初の要素から順番に調べていく、というものはないでしょうか。線形探索とはこのアルゴリズムのことです。

探索には n をリストの長さとして O(n) の計算時間量になります。

例を示すまでもないでしょうけれども、念のためにコードを載せておきます。

search/list/LinearSearch.java

package search.list;

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

public class LinearSearch {

    public static  int search(List list, T target,
            Comparator comparator) {
        for (int i = 0; i < list.size(); i++) {
            if (comparator.compare(list.get(i), target) == 0) {
                return i;
            }
        }
        return -1;
    }

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

    private static  void showResult(List list, int result) {
        if (result < 0) {
            System.out.println("object not found");
        } else {
            System.out.println("object found");
            System.out.println("index: " + result + ", value: "
                    + list.get(result));
        }
    }

    public static void main(String... args) {
        List list = new ArrayList();
        for (int i = 0; i < 1000; i++) {
            list.add(i);
        }
        Collections.shuffle(list);

        System.out.println("リストの中から値が0のオブジェクトを探索");
        showResult(list, search(list, 0));

        System.out.println();
        System.out.println("リストの中から値が1000のオブジェクトを探索");
        showResult(list, search(list, 1000));

        Comparator gec = new Comparator() {
            @Override
            public int compare(Integer a, Integer b) {
                return a >= b ? 0 : 1;
            }
        };

        System.out.println();
        System.out.println("リストの中から値が990以上のオブジェクトを探索");
        showResult(list, search(list, 990, gec));

        System.out.println();
        System.out.println("リストの中から値が1000以上のオブジェクトを探索");
        showResult(list, search(list, 1000, gec));
    }

    private static class DefaultComparator>
            implements Comparator {

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

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