感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

Javaで線形探索

<スポンサーリンク>

線形探索は非常に単純な探索方法で、簡単にいうと、配列の前から順番に探していくだけ。

柴田先生の本でいうと、

要素が直線上に並んだ配列からの探索は、目的とするキー値を持つ要素に出会うまで先頭から順に要素を走査することによって実現できます。

となっている。

図にするとこんな感じ。
f:id:sho322:20131215204617j:plain
CANSAY NUboard

サンプルのプログラムを動かしてみる。

package algorithm.search;

import java.util.Random;

public class SequentialSearch {
    public static int seqSearch(int[] array, int target) {
        int i = 0;
        int size = 0;
        if (array != null) {
            size = array.length;
        } else {
            return -1;
        }
        
        while (true) {
            if (i == size) {
                return -1;
            }
            if (array[i] == target) {
                return i;
            }
            i++;
        }
    }

    public static void main(String[] args) {
        int max = 1000000;
        int keyNum = 777;
        int[] array = new int[max];
        Random rnd = new Random();
        
        //max分配列に値をつっこむ
        for (int i = 0; i < max; i++) {
            array[i] = rnd.nextInt(1000000);
        }
        
        long start = System.nanoTime();
        int index = seqSearch(array, keyNum);
        long end = System.nanoTime();
        if (index != -1) {
            System.out.println("探したかった数字→" + keyNum + " は" + index + "番目にあります!");
            System.out.println("array[index]→" + array[index]);
        } else {
            System.out.println("探してた数字→" + keyNum + "はねぇよ");
        }

        //数が少ない場合はlong t1 = System.nanoTime();を使った方がいい
        System.out.println("かかった時間は・・・:" + (end - start) + "ナノ秒");
    }
}

結果はこうなる。

探したかった数字→777 は684604番目にあります!
array[index]→777
かかった時間は・・・:3756696ナノ秒

図にも書いたけど、これにはちょっと非効率なところがあって、それを解決するために「番兵法」というのがあるのだけれど、それはまた後日。

参考にした本

明解 Javaによるアルゴリズムとデータ構造

明解 Javaによるアルゴリズムとデータ構造