テクノロジー編26: アルゴリズム

配列やリストなどのデータ構造から特定の要素を順番に探していく最も基本的な探索方法。
計算量は O(n) で、最悪の場合は全ての要素を調べる必要がある。

線形探索法は、データが小さい場合や、データの並び順が特に決まっていない場合に有効。

int[] A = {3, 1, 4, 5, 2};
int n = A.length; // 配列の長さ
int x = 4;        // 探したい要素

for (int i = 0; i < n; i++) {
  if (A[i] == x) {
    System.out.println("要素 " + x + " を発見しました。インデックス: " + i);
    return;
  }
}
System.out.println("要素 " + x + " は配列に存在しません。");

ソートされたデータに対して効率的に要素を探索するアルゴリズム。
探索範囲を半分ずつに絞り込みながら探索をおこなう。
最悪の場合でも時間計算量は O(log n)。

データの量が膨大になっても効率的に探索できるため、非常に有用。

int[] A = {1, 2, 3, 4, 5}; // ソートされた配列
int n = A.length; // 配列の長さ
int x = 4;        // 探したい要素

int left = 0;    // 左端
int right = n - 1; // 右端
while (left <= right) {
  // 中央のインデックスを計算
  int mid = (left + right) / 2;
  if (A[mid] == x) {
    System.out.println("要素 " + x + " を発見しました。インデックス: " + mid);
    return;
  } else if (A[mid] < x) {
    // 探索範囲を右側に絞り込む
    left = mid + 1;
  } else {
    // 探索範囲を左側に絞り込む
    right = mid - 1;
  }
}
System.out.println("要素 " + x + " は配列に存在しません。");

ハッシュ関数を用いて、データを効率的に格納・検索する方法。
ハッシュ衝突時に対処するため、オープンアドレス法やチェイン法などの手法がある。

オープンアドレス法は、ハッシュ表の空いている場所を探して要素を格納する方法。
チェイン法は、ハッシュ値が同じ要素をリストなどで管理する方法。

ハッシュがほとんど衝突しない場合には O(1) で探索できるが、衝突が多い場合は O(n) になることもある。

int hashFunction(int key) { return key % 3; } // ハッシュ関数
int[] hashTable = new int[3]; // ハッシュ表

int[] A = {3, 1, 4};
for (int i = 0; i < A.length; i++) {
  int index = hashFunction(A[i]);
  while (hashTable[index] != 0) {
    index = (index + 1) % hashTable.length; // 次のインデックスへ
  }
  hashTable[index] = A[i]; // ハッシュ表に要素を格納
}

int x = 4; // 探したい要素
for (int i = 0; i < hashTable.length; i++) {
  if (hashTable[i] == x) {
    System.out.println("要素 " + x + " を発見しました。インデックス: " + i);
    return;
  }
  if (hashTable[i] == 0) {
    // 空の部分があれば探索終了
    break;
  }
}
System.out.println("要素 " + x + " はハッシュ表に存在しません。");

import java.util.LinkedList;
import java.util.List;
int hashFunction(int key) { return key % 3; } // ハッシュ関数
List<Integer>[] hashTable = new LinkedList[3]; // ハッシュ表
for (int i = 0; i < hashTable.length; i++) {
  hashTable[i] = new LinkedList<>(); // 各バケットを初期化
}
int[] A = {3, 1, 4};
for (int i = 0; i < A.length; i++) {
  int index = hashFunction(A[i]);
  hashTable[index].add(A[i]); // ハッシュ表に要素を格納
}
int x = 4; // 探したい要素
for (int i = 0; i < hashTable.length; i++) {
  if (hashTable[i].contains(x)) {
    System.out.println("要素 " + x + " を発見しました。バケット: " + i);
    return;
  }
}
System.out.println("要素 " + x + " はハッシュ表に存在しません。");