ホームページ > 記事 > Java > Java の BinarySearch()

Java の BinarySearch()

WBOYオリジナル: 2024-08-30 16:12:22970ブラウズ

Java の binarySearch() は、二分探索アルゴリズムを使用して複数の要素から特定のキー要素を検索するのに役立つメソッドです。この操作を実行するには、要素を昇順に並べ替える必要があります。ソートされていない場合は、Arrays.sort(arr) メソッドを使用してソートできます。それ以外の場合、結果は未定義であると言われます。線形探索と比較して、二分探索は高速であると考えられています。このため、二分探索の時間計算量は O(log n) と言われます。さらに、binarySearch() メソッドは java.util.Arrays パッケージからインスタンス化できます。 binarySearch() メソッドの詳細については、次のセクションで説明します。

構文:

無料ソフトウェア開発コースを始めましょう

Web 開発、プログラミング言語、ソフトウェアテスト、その他

public static int binarySearch(Object[] a, Object key)

ここで、パラメータ a と key はそれぞれ、検索する必要がある配列と見つける必要がある値です。

binarySearch() メソッドは、検索していたキー要素のインデックスを返します。キー要素が見つからない場合は、挿入されるはずだったキー要素が挿入される挿入ポイントが返されます。検索のキー要素が配列内の他の要素と比較できない場合、ClassCastException として知られる例外がスローされます。

Java での BinarySearch() メソッドはどのように機能しますか?

このメソッドが Java でどのように機能するかを見てみましょう:

k が検索する必要があるキー要素であると仮定します。 k を配列の中央の要素と比較します。
k が中間位置の要素と一致する場合、中間インデックスを返す必要があります。
そうでない場合、k が中央の位置の要素よりも高い場合、k は中央の要素の右側でのみ見つかります。
それ以外の場合は、中央の要素の左側にあります。

Java で BinarySearch() を実装する例

以下は、BinarySearch() メソッドに関するいくつかのプログラムの例です。

例 #1

コード:

import java.util.Arrays;
public class BinarySearchExample
{
public static void main(String[] args)
{
//create a byte array
byte ba[] = {05, 10, 15, 20, 25, 30};
//create a character array
char ca[] = {'a', 'n', 's', 'p', 'v', 'i', 'd'};
//create an integer array
int ia[] = { 10, 20, 15, 22, 35};
//create a double array
double da[] = {10.1 , 15.34 , 22.25, 13.5};
//create a float array
float fa[] = {13.2f, 25.1f , 22.2f , 43.5f };
//sort all the arrays that created above
Arrays.sort(ba);
Arrays.sort(ca);
Arrays.sort(ia);
Arrays.sort(da);
Arrays.sort(fa);
//enter the key elements that has to be searched in the array
byte bKey = 15;
char cKey = 'i';
int iKey = 22;
double dKey = 15.34;
float fKey = 22.2f;
System.out.println("Element "+ bKey + " is found at the position of " + Arrays.binarySearch(ba,bKey) );
System.out.println("Element "+ cKey + " is found at the position of " + Arrays.binarySearch(ca,cKey) );
System.out.println("Element "+ iKey + " is found at the position of " + Arrays.binarySearch(ia,iKey) );
System.out.println("Element "+ dKey + " is found at the position of " + Arrays.binarySearch(da,dKey) );
System.out.println("Element "+ fKey + " is found at the position of " + Arrays.binarySearch(fa,fKey) );
}
}

出力:

Java の BinarySearch()

文字、整数、浮動小数点、倍精度浮動小数点、バイトなどのさまざまな型の特定の配列は、上記のプログラムで配列を使用して配列を並べ替えた後に作成されます。Sort() メソッドでは、配列内で検索する必要がある要素が宣言されます。次に、検索された要素のインデックスが Arrays.binarySearch() メソッドを使用して出力されます。

配列に存在しないキー要素が指定されたとします。出力は何になりますか??

それを見つけるために、以下に示すように主要な要素のコードを変更してみましょう。

バイト bKey = 15;
char cKey = 'i';
int iKey = 89;
double dKey = 15.34;
float fKey = 22.2f;

つまり、iKey=89 が配列に存在しない場合、出力は次のように表示されます。

Java の BinarySearch()

ご覧のとおり、位置は -6 として出力されます。これは、要素が検索されて見つからなかった場合、その要素が存在していればインデックスの負の値が返されるためです。つまり、int ia[] = { 10, 20, 15, 22, 35} は指定された配列です。 89 が存在する場合、配列は int ia[] = { 10, 20, 15, 22, 35, 89};

になります。

インデックスが 6 であることが明確にわかります。元の配列には存在しないため、その特定のインデックスの負の値が上記の出力で返されます。

例 #2

次に示すように、再帰を利用して二分探索を行うこともできます。

コード:

//sample class
class BinarySearchExample{
public static int binarySearch(int a[], int f, int l, int k){
//if last element is greater than or equal to first element
if (l>=f)
{
//find the mid
int m = f + (l - f)/2;
//if the key element that is searching is found in middle position, return mid position
if (a[m] == k)
{
return m;
}
//if key element is less than element in middle position, search the left <u>subarray</u>
if (a[m] > k){
return binarySearch(a, f, m-1, k);
}
//if key element is greater than the element in middle position, search the right <u>subarray</u>
else{
return binarySearch(a, m+1, l, k);
}
}
return -1;
}
public static void main(String args[]){
//initialise the array
int a[] = {34,45,54,68,79};
int k = 68;
int l = a.length-1;
//store the position in variable res
int res = binarySearch(a,0,l,k);
if (res == -1)
System.out.println("Sorry!! Can't find the element....!");
else
System.out.println("Element is found at the position: "+res);
}
}

出力:

Java の BinarySearch()

上記のプログラムでは、まず配列を作成し、求めたい要素も宣言しています。 binarySearch() メソッドを使用すると、キー要素の位置がわかります。要素が見つからない場合は、「申し訳ありません !!!要素が見つかりません」というメッセージが表示されます。

結論

binarySearch() は、二分探索アルゴリズムを使用して、配列内で使用可能な複数の要素の中から特定のキー要素を検索するのに役立つ Java メソッドです。このメソッドの動作と例は、このドキュメントで詳しく説明されています。

Java の BinarySearch()

Java での BinarySearch() メソッドはどのように機能しますか?

Java で BinarySearch() を実装する例

例 #1

例 #2

結論

おすすめ記事

関連記事