コーヒーブレイク#156。Java で Arrays.binarySearch() メソッドを使用する方法

出典: FreeCodeCamp この記事では、Java で Arrays.binarySearch() メソッドを使用する方法を学びます。

Java の Arrays.binarySearch() とは何ですか?

Arrays.binarySearch()メソッドの公式ドキュメントには次のように記載されています。

• このメソッドは、二分探索アルゴリズムを使用して、指定されたバイト配列で指定された値を検索します。
• 呼び出しを行う前に、配列をソートする必要があります ( sort(byte[])メソッドを使用)。ソートされていない場合、結果は決まりません。
• 配列に指定された値を持つ複数の要素が含まれている場合、どれが見つかるかという保証はありません。

簡単に言えば、Arrays.binarySearch()メソッドは、並べ替えられた配列内の特定の要素を検索し、見つかった場合はそのインデックスを返すことができます。

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';

		int foundItemIndex = Arrays.binarySearch(vowels, key);

		System.out.println("The given vowel is at index: " + foundItemIndex);

	}
}

Arrays.binarySearch() メソッドは、最初の引数として検索する配列を受け取り、2 番目の引数として検索するキーを受け取ります。上記のプログラムの出力は次のようになります。 このメソッドは要素自体ではなく、見つかった要素のインデックスを返すことに注意してください。こうすることで、この例で使用されているように、インデックスを整数として保存できます。デフォルトでは、このメソッドは配列の最初のインデックスを検索の開始点として使用し、配列の長さを検索の終了点として使用します。この場合、開始インデックスは 0 で、終了インデックスは 6 です。デフォルトの開始インデックスと終了インデックスを使用する代わりに、それらを自分で定義できます。たとえば、インデックス 2 からインデックス 4 まで検索したい場合は、次のように実行できます。

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';
		int startIndex = 2;
		int endIndex = 4;

		int foundItemIndex = Arrays.binarySearch(vowels, startIndex, endIndex, key);

		System.out.println("The given vowel is at index: " + foundItemIndex);

	}
}

この場合、Arrays.binarySearch()メソッドは、検索する配列を最初の引数として、開始インデックスを 2 番目の引数として、終了インデックスを 3 番目の引数として、キーを 4 番目の引数として受け取ります。終了インデックスが配列の長さ内に収まっている限り、このメソッドは正常に機能するはずです。ただし、それを超えると、配列インデックスが範囲外の例外が発生します。とてもシンプルですね。このメソッドは、要素が見つかった場合はそのインデックスを返します。しかし、指定された要素が見つからない場合はどうなるでしょうか?

Arrays.binarySearch() で指定された要素が見つからない場合はどうなりますか?

Arrays.binarySearch()メソッドの公式ドキュメントをもう一度見てみましょう。

• このメソッドは、キーが指定された範囲内の配列に含まれている場合、検索結果でキーのインデックスを見つけます。それ以外の場合は、 (-(挿入ポイント) - 1)を取得します。
• 挿入ポイントは、キーが配列に挿入されるポイントとして定義されます。範囲内の最初の要素のインデックスがキーより大きいか、範囲内のすべての要素がキーより小さい場合は toIndex (終了インデックス) です。指定されたキー。
• キーが見つかった場合、戻り値は 0 以上になることに注意してください。

あまり明確ではありませんよね？最初の行は、キーが配列内で見つかった場合、メソッドが検索からそのキーのインデックスを返すことを示しています。見つからない場合、出力は値(-(挿入ポイント) - 1)と等しくなります。検索キーに応じて、挿入ポイントの意味が異なる場合があります。配列[5, 6, 7, 8, 9, 10]と検索キー0 があるとします。これは明らかに配列内にありません。この場合、検索キーは配列のすべての要素よりも小さくなります。ただし、検索キーより大きい最初の要素は5です。したがって、この場合、挿入ポイントは次のようになります。 これは次のようなコード スニペットで実装できます。

package arrays;

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		System.out.println(Arrays.binarySearch(numbers, 0)); // -1
	}
}

もう一度、配列[5, 6, 7, 8, 9, 10]と検索キー12があると仮定します。これは明らかに配列内にありません。この場合、検索キーは配列のすべての要素よりも大きくなります。ここでの挿入ポイントは次のようになります。 終了インデックスを手動で指定しない場合、メソッドは配列の長さを終了インデックスとして使用することに注意してください。この場合は6です。これは次のようなコード スニペットで実装できます。

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		System.out.println(Arrays.binarySearch(numbers, 12)); // -7
	}
}

ただし、開始インデックスと終了インデックスを手動で定義すると、結果が変わります。

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		int startIndex = 1;
		int endIndex = 3;

		System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 5)); // -2
		System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 10)); // -4

	}
}

自分で値を計算してみてください。次のようなシンボルを使用してArrays.binarySearch()メソッドを使用することもできます。

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';
		int startIndex = 2;
		int endIndex = 4;

		System.out.println(Arrays.binarySearch(vowels, startIndex, endIndex, key));

	}
}

指定された検索キーが見つからない場合にも、同じ原則が適用されます。ただし、配列内の文字と特定の検索キーを比較する場合は、対応する文字の ASCII コードが使用されます。つまり、A (65) はa (97)より小さくなります。プログラムの出力をクロスチェックするときは、これを考慮してください。