探索アルゴリズム

線形探索（Linear Search）

配列の先頭から順番に1つずつ確認していく最もシンプルな探索方法です。 計算量は O(n) で、ソートされていないデータにも使えます。

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // 見つかったインデックスを返す
    }
  }
  return -1; // 見つからなかった
}

const data = [4, 2, 7, 1, 9, 3];
console.log(linearSearch(data, 7)); // 2
console.log(linearSearch(data, 5)); // -1

二分探索（Binary Search）

ソート済みの配列に対して、 中央の要素と比較して探索範囲を半分に絞り込んでいく方法です。 計算量は O(log n) で、線形探索よりはるかに高速です。

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // 見つかった
    } else if (arr[mid] < target) {
      left = mid + 1; // 右半分を探索
    } else {
      right = mid - 1; // 左半分を探索
    }
  }

  return -1; // 見つからなかった
}

// ソート済みの配列が必要
const sorted = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sorted, 7));  // 3
console.log(binarySearch(sorted, 6));  // -1

100万件のデータでも最大約20回の比較で見つかります（2^20 > 1,000,000）。

幅優先探索（BFS: Breadth-First Search）

グラフや木構造を探索するアルゴリズムで、スタート地点に近いノードから順番に探索します。 キューを使って実装し、最短経路を見つけるのに適しています。

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift(); // 先頭を取り出す
    result.push(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return result;
}

// グラフの隣接リスト表現
const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"],
};

console.log(bfs(graph, "A"));
// ["A", "B", "C", "D", "E", "F"]

深さ優先探索（DFS: Depth-First Search）

1つの経路をできるだけ深く進み、 行き止まりになったら戻って別の経路を探索します。 スタックまたは再帰を使って実装し、全経路の探索やサイクル検出に適しています。

// 再帰版DFS
function dfs(graph, node, visited = new Set()) {
  visited.add(node);
  const result = [node];

  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      result.push(...dfs(graph, neighbor, visited));
    }
  }

  return result;
}

// スタック版DFS
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const result = [];

  while (stack.length > 0) {
    const node = stack.pop(); // 末尾を取り出す
    if (visited.has(node)) continue;

    visited.add(node);
    result.push(node);

    // 隣接ノードをスタックに追加
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }

  return result;
}

const graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"],
};

console.log(dfs(graph, "A"));
// ["A", "B", "D", "E", "F", "C"]

BFS vs DFS の比較