close

二分探索 (Binary Search) アルゴリズム Java

二分探索アルゴリズムは Java プログラミングにおける効率的な方法であり、ソートされた配列内で特定の値を見つけるために使用されます。 このアプローチでは、配列を継続的に 2 つの部分に分割し、検索値を中央の要素と比較します。

二分探索アルゴリズムの仕組み

二分検索アルゴリズムは、検索値を配列の中央の要素と比較することから始まります。 検索値が中央の要素と等しい場合、アルゴリズムはその要素の位置を返します。 検索値が中央の要素より小さい場合、アルゴリズムは配列の左半分で検索を続けます。 検索値が大きい場合、アルゴリズムは配列の右半分で検索を続けます。 このプロセスは、検索値が見つかるか、検索する要素がなくなるまで繰り返されます。

二分探索アルゴリズムの長所と短所

利点:

  • 高効率: このアルゴリズムは各ステップの要素の半分を削除し、大きな配列の検索を最適化します。
  • 低い時間計算量: このアルゴリズムの時間計算量は O(log n) であるため、大規模なデータセットに対して効果的です。

短所:

  • ソートされた配列の要件: このアルゴリズムはソートされた配列でのみ機能します。

例と説明

二分探索アルゴリズムを使用して、 のソートされた整数配列から特定の整数を見つける例を考えてみましょう Java。 

public class BinarySearchExample {  
    public static int binarySearch(int[] array, int target) {  
        int left = 0;  
        int right = array.length- 1;  
  
        while(left <= right) {  
            int mid = left +(right- left) / 2;  
  
            if(array[mid] == target) {  
                return mid; // Return position if found  
            } else if(array[mid] < target) {  
                left = mid + 1;  
            } else {  
                right = mid- 1;  
            }  
        }  
        return -1; // Return -1 if not found  
    }  
  
    public static void main(String[] args) {  
        int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15 };  
        int target = 9;  
  
        int position = binarySearch(numbers, target);  
  
        if(position != -1) {  
            System.out.println("Element " + target + " found at position " + position);  
        } else {  
            System.out.println("Element " + target + " not found in the array");  
        }  
    }  
}

この例では、二分探索アルゴリズムを使用して、ソートされた整数配列内で数値 9 を見つけます。 アルゴリズムは配列を反復処理し、検索値を中央の値と比較します。 この場合、数値 9 は配列内の位置 4(0 から始まるインデックス) で見つかります。

この例は、バイナリ検索アルゴリズムがソートされた整数配列内の要素を見つける方法を示していますが、プログラミングの他の検索シナリオにも適用できます Java。