JavaScript と Java で二分検索をマスターする: ステップバイステップ ガイド

二分探索は、すべての開発者が理解すべき基本的なアルゴリズムであり、並べ替えられた配列内の要素を検索する非常に効率的な方法を提供します。このアルゴリズムは「分割統治」アプローチに依存しており、ステップごとに検索スペースを半分にすることができます。この記事では、JavaScript と Java の両方でバイナリ検索を検討し、反復実装と再帰実装について説明します。

二分探索とは何ですか?

二分探索は、ソートされた配列内でターゲット値の位置を見つけるように設計されたアルゴリズムです。配列のソートされた性質を利用することにより、バイナリ検索は効率的に検索空間を絞り込み、O(log n) の時間計算量を達成します。これは、大規模なデータセットの線形検索よりもはるかに高速です。

大まかな概要は次のとおりです:

1. 現在の検索範囲を表す 2 つのポインター startIndex と endIndex で開始します。
2. startIndex と endIndex の間の中間インデックス (midIndex) を計算します。
3. 中央の要素をターゲットと比較します。
   • ターゲットと一致する場合は、インデックスを返します。
   • 中央の要素がターゲットより大きい場合、ターゲットは左半分にある必要があるため、endIndex を調整します。
   • 中央の要素がターゲットより小さい場合、ターゲットは右半分にある必要があるため、startIndex を調整します。
4. ターゲットが見つかるか、startIndex が endIndex を超えて、ターゲットが配列内にないことを示すまで、このプロセスを繰り返します。

コード例を見てみましょう。

JavaScript および Java の反復二分探索

JavaScriptの実装

JavaScript では、反復アプローチではループを使用して二分探索を実行します。これは次のようになります:

const binarySearch = (arr, target) => {
  let startIndex = 0;
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] === target) {
      return midIndex; // Target found
    } else if (arr[midIndex] < target) {
      startIndex = midIndex + 1; // Search in the right half
    } else {
      endIndex = midIndex - 1; // Search in the left half
    }
  }
  return -1; // Target not found
};

let nums = [-1, 0, 3, 5, 9, 12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

Javaの実装

Java では、反復実装は非常に似ていますが、Java 構文に合わせて調整されています。

public class BinarySearchExample {

    public static int binarySearch(int[] arr, int target) {
        int startIndex = 0;
        int endIndex = arr.length - 1;

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;

            if (arr[midIndex] == target) {
                return midIndex; // Target found
            } else if (arr[midIndex] < target) {
                startIndex = midIndex + 1; // Search in the right half
            } else {
                endIndex = midIndex - 1; // Search in the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;

        int result = binarySearch(nums, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

説明

両方の実装:

• startIndex と endIndex をそれぞれ配列の先頭と末尾に設定します。
• 各反復では、中間インデックス (midIndex) を見つけ、arr[midIndex] をターゲットと比較します。
  • arr[midIndex] が target と等しい場合、midIndex を返します。
  • arr[midIndex] がターゲットより小さい場合、startIndex をmidIndex 1 に移動し、検索を右半分に絞り込みます。
  • arr[midIndex] が target より大きい場合、endIndex をmidIndex - 1 に移動し、検索を左半分に絞り込みます。
• startIndex が endIndex を超える場合、つまりターゲットが配列内にない場合、ループは終了します。

JavaScript および Java での再帰的二分探索

再帰的アプローチの場合、ターゲットが見つかるか検索範囲が空になるまで、更新されたインデックスで自分自身を呼び出すように関数を定義します。

JavaScriptの実装

JavaScript での再帰二分検索の実装は次のとおりです。

const binarySearch = (arr, target) => {
  let startIndex = 0;
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] === target) {
      return midIndex; // Target found
    } else if (arr[midIndex] < target) {
      startIndex = midIndex + 1; // Search in the right half
    } else {
      endIndex = midIndex - 1; // Search in the left half
    }
  }
  return -1; // Target not found
};

let nums = [-1, 0, 3, 5, 9, 12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

Javaの実装

Java では、同様の再帰的二分検索を次のように実装できます。

public class BinarySearchExample {

    public static int binarySearch(int[] arr, int target) {
        int startIndex = 0;
        int endIndex = arr.length - 1;

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;

            if (arr[midIndex] == target) {
                return midIndex; // Target found
            } else if (arr[midIndex] < target) {
                startIndex = midIndex + 1; // Search in the right half
            } else {
                endIndex = midIndex - 1; // Search in the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;

        int result = binarySearch(nums, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

再帰的バージョンの仕組み

各再帰呼び出し内:

• 中間インデックス、midIndex が計算されます。
• arr[midIndex] がターゲットと一致する場合、インデックスを返します。
• arr[midIndex] がターゲットより大きい場合、検索は左半分で続行されます (endIndex は MidIndex - 1 になります)。
• arr[midIndex] がターゲットより小さい場合、検索は右半分で続行されます (startIndex は MidIndex 1 になります)。
• 基本ケース if (startIndex > endIndex) では、ターゲットが見つからない場合に再帰が確実に停止されます。

  ---

  複雑さの分析

  • 時間計算量: 各ステップで検索スペースが半分になるため、反復バージョンと再帰バージョンの両方の時間計算量は O(log n) です。
  • 空間の複雑さ: 反復アプローチでは空間の複雑さが O(1) ですが、再帰的アプローチではコール スタックにより空間の複雑さが O(log n) になります。

  二分検索を使用する場合

  二分検索は次の場合に最適です。

  • 配列はソートされています: 二分検索はソートされた配列でのみ機能します。
  • 効率は重要です: 時間計算量が O(log n) であるため、大規模なデータセットでは非常に効率的です。

  配列がソートされていない場合は、最初にソートするか (コスト O(n log n) で)、データセットが小さい場合は線形検索を使用することを検討してください。

  ---

  結論

  二分探索は、ソートされた配列内の要素を見つけるための多用途かつ効率的なアルゴリズムです。反復的アプローチを選択するか再帰的アプローチを選択するかに関係なく、バイナリ検索を理解することは、アプリケーションのパフォーマンスを向上させるのに役立ちます。 JavaScript と Java の両方の実装を試して、その動作の感触をつかみ、特定のユースケースにどちらが最適であるかを確認してください。

  ---

  ?参照

  • 二分探索
  • グルックアルゴリズム
  • ビッグオー表記

  ?私に話して

  • リンクトイン
  • Github
  • ポートフォリオ

  以上がJavaScript と Java で二分検索をマスターする: ステップバイステップ ガイドの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。