JavaScript での二分探索

二分検索は、ソートされたリスト内の特定の要素の位置を見つけるために使用される検索アルゴリズムです。目的の要素が見つかるか、要素がリストに存在しないと判断されるまで、リストを繰り返し半分に分割することによって機能します。

二分探索はどのように機能しますか?

二分探索の仕組みを理解するために、例を考えてみましょう。ソートされた整数のリストがあり、数字 37 の位置を見つけたいとします。二分探索アルゴリズムは次のように機能します。

1. まず、リストの中間要素を決定します。中央の要素が 37 の場合、処理は完了し、要素の位置を返します。
2. 中央の要素が 37 でない場合は、それが 37 より大きいか小さいかを確認します。37 より大きい場合は、目的の要素がリストの左半分にある必要があることがわかります。37 未満の場合、目的の要素はリストの右半分にある必要があることがわかります。
3. 要素が見つかるか、要素がリストに存在しないと判断されるまで、リストの適切な半分でプロセスを繰り返します。

function binarySearch(arr, x) {
  let start = 0;
  let end = arr.length - 1;
  
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    
    if (arr[mid] === x) {
      return mid;
    }
    else if (arr[mid] < x) {
      start = mid + 1;
    }
    else {
      end = mid - 1;
    }
  }
  
  return -1;
}

let arr = [1, 3, 5, 7, 9, 11, 13];
let x = 5;

console.log(binarySearch(arr, x)); // Output: 2

なぜバイナリ検索を使用する必要があるのですか?

では、なぜバイナリ検索を使用する必要があるのでしょうか。二分探索の主な利点の 1 つは、その時間の複雑さです。最悪のシナリオでは、二分探索の時間計算量は O(log n) です。これは、大きなリストの線形探索 (O(n)) よりもはるかに高速であることを意味します。これにより、大規模なデータセットを検索するための効率的なアルゴリズムになります。

結論として、二分探索は、ソートされたリスト内の特定の要素の位置をすばやく見つけるための便利なアルゴリズムです。その時間の複雑さにより、大規模なデータセットの検索に適しており、JavaScript での実装は比較的簡単です。