はじめに
二分探索は、ソート済み配列内の値を見つけるために使用される効率的な探索アルゴリズムです。線形探索よりも高速であり、各反復ごとに配列の半分を除外するためです。この実験では、Java で二分探索アルゴリズムを実装する手順を学びます。
二分探索は、ソート済み配列内の値を見つけるために使用される効率的な探索アルゴリズムです。線形探索よりも高速であり、各反復ごとに配列の半分を除外するためです。この実験では、Java で二分探索アルゴリズムを実装する手順を学びます。
二分探索アルゴリズムにはソート済み配列が必要ですので、まずソート済み配列を作成します。
int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
ここでは、反復的に二分探索アルゴリズムを実装します。このメソッドは、要素が配列に存在する場合にはその要素のインデックスを返します。そうでない場合は、-1 を返します。
public static int binarySearchIterative(int[] sortedArray, int key) {
int leftIdx = 0;
int rightIdx = sortedArray.length - 1;
while (leftIdx <= rightIdx) {
int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
if (sortedArray[midIdx] == key)
return midIdx;
else if (sortedArray[midIdx] > key) {
rightIdx = midIdx - 1;
} else
leftIdx = midIdx + 1;
}
return -1;
}
コードを実行するには、まず binarySearchIterative
メソッドを呼び出し、sortedArray
と検索したい要素をパラメータとして渡す必要があります。
## javaファイルをコンパイルする
javac BinarySearch.java
## ファイルを実行する
java BinarySearch
ここでは、再帰的に二分探索アルゴリズムを実装します。このメソッドも、要素が配列に存在する場合にはその要素のインデックスを返します。そうでない場合は、-1 を返します。
public static int binarySearchRecursive(int[] sortedArray, int key, int leftIdx, int rightIdx) {
if (leftIdx <= rightIdx) {
int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
if (sortedArray[midIdx] == key)
return midIdx;
else if (sortedArray[midIdx] > key) {
return binarySearchRecursive(sortedArray, key, leftIdx, midIdx - 1);
} else
return binarySearchRecursive(sortedArray, key, midIdx + 1, rightIdx);
} else
return -1;
}
コードを実行するには、binarySearchRecursive
メソッドを呼び出し、sortedArray
、検索したい要素、leftIdx
、および rightIdx
をパラメータとして渡す必要があります。
Java には二分探索を実装するための組み込み関数もあります。これらの関数は Arrays.binarySearch()
と Collections.binarySearch()
です。これらの関数を使って、ソート済み配列内の要素を検索することができます。
Arrays.binarySearch()
関数は、ソート済み配列と検索するキー値をパラメータとして取ります。この関数は、キーが配列に存在する場合にはそのキーのインデックスを返します。そうでない場合は、-1 を返します。
int index = Arrays.binarySearch(sortedArray, 6);
Collections.binarySearch()
関数は、ArrayList のようなコレクションに対して要素を検索するために使用できます。この関数は、ソート済みのコレクションとキーをパラメータとして取り、キーが存在するインデックスを返します。そうでない場合は、-1 を返します。
ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
int index = Collections.binarySearch(sortedList, 6);
ここでは、すべてのメソッドをテストして出力を表示します。
public static void main(String[] args) {
int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int key = 12;
System.out.println("Element " + key + " is present at index: " + binarySearchIterative(sortedArray, key));
System.out.println("Element " + key + " is present at index: " + binarySearchRecursive(sortedArray, key, 0, sortedArray.length - 1));
System.out.println("Element " + key + " is present at index: " + Arrays.binarySearch(sortedArray, key));
ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
System.out.println("Element " + key + " is present at index: " + Collections.binarySearch(sortedList, key));
}
コードを実行するには、まず Java プログラムをコンパイルします。
javac BinarySearch.java
その後、プログラムを実行できます。
java BinarySearch
この実験では、Java プログラミング言語で反復的および再帰的に二分探索アルゴリズムを実装するための必要な手順について説明しました。また、二分探索を実装するための組み込みメソッド Arrays.binarySearch()
と Collections.binarySearch()
についても学びました。ソート済み配列を作成し、その中の要素を検索するためにさまざまなメソッドを使用しました。