1.1 線形探索

探索とは

　表の中から特定のID(Keyを)持つデータを探す動作のことである．

線形探索

　探索の最もシンプルなアルゴリズムとして線形探索が ある．この探索法では，表の最初から順に，探索対象となるIDを見るけるまで探す というものだ．

実装例

　線形探索は以下のコードのように実装することができる．

for(int i=0; <datanum; i++){
    if(strcmp(data[i].getKey(), key) == 0){
        return i;
    }
}
        

public class LinearSearch {
    static int[] table = { 4, 2, 11, 4, 3, 2, 35, 3535, 353535 };

    static int linearSearch(int key) {
        for (int i = 0; i < table.length; i++) {
            if (table[i] == key) {
                return i;
            }
        }
        return -1;
    }

    static void printArray() {
        System.out.print("table = {");
        for (int i = 0; i < table.length; i++) {
            System.out.printf("%d", table[i]);
            if (i != table.length - 1) {
                System.out.printf(", ");
            }
        }
        System.out.println("}");
    }

    public static void main(String[] args) {
        int key = 3535;
        System.out.printf("key = %d\n",key);
        printArray();
        int index = linearSearch(key);
        if (index != -1) {
            System.out.printf("key == table[%d]", index);
        } else {
            System.out.println("could not find key(3535)");
        }
    }

}

        

$ java LinearSearch

table = {4, 2, 11, 4, 3, 2, 35, 3535, 353535}
key == table[7]

計算量

• 探索：O(n)
　0番目から1個ずつ探さないといけないため，最悪でデータの個数だけ 比較が必要である．
• 削除：O(n)
　そのデータが保存されているか探索し，存在した場合は削除したデータ 以降を詰める作業も必要である．
• 挿入：O(1)
　data[datanum]に新規データを保存すればいいため，保存されている データ数に依存しない．