HOWTO · Java
Java 二分探索の反復的および再帰的
このチュートリアルでは、二分探索アルゴリズムの使用方法を説明します。
このページの内容
注意
二分探索を詳しく理解したい場合は、二分探索アルゴリズムの記事を参照してください。
反復二分探索アルゴリズム
ここでは、n の要素を含むソートされていない配列 A[] があると仮定して、要素 X を見つけたいとします。
-
loを0とし、hiをn - 1とする。 -
lo<hiの間：mid=lo + (hi - lo)/2とします。A[mid] == Xの場合は、要素が見つかったのでインデックスmidを返します。A[mid] < Xの場合は、左半分の要素を破棄してloをmid+1とします。- そうでない場合は、
A[mid] > Xの場合は、右半分の要素を破棄してhiをmid-1とします。
-
要素が見つからないので
-1を返す。
二分探索のための Java 反復プログラム
class BinarySearch {
int binarySearch(int arr[], int x) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
lo = mid + 1;
else
hi = mid - 1;
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = {1, 2, 3, 4, 5};
int n = arr.length;
int x = 5;
int position = ob.binarySearch(arr, x);
if (position == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index: " + position);
}
}
出力：
Element found at index: 4
再帰的二分探索アルゴリズム
ここでは、n 個の要素を含むソートされていない配列 A[] があり、その中から X 個の要素を見つけたいとします。
-
loを0、hiをn-1として初期化する。 -
lo>hiの場合は、配列の探索空間を使い切ったことになるので、-1 を返す。 -
中間点
midをlo+(hi-lo)/2として計算する。配列を 2つに分割します。下半分の0からmid - 1までの要素を持つ配列と、上半分のmidからn - 1までの要素を持つ配列です。 -
X==midならば、対象となる要素が見つかったことになります。 -
Xがmidよりも小さい場合は、binarysearch(arr, lo, mid-1)を再帰的に呼び出して配列の下半分を検索する。 -
それ以外の場合、
Xがmidより大きい場合は、binarysearch(arr, mid+1, hi)を再帰的に呼び出して配列の上半分を検索する。
二分探索のための Java 再帰プログラム
class BinarySearch {
int binarySearch(int arr[], int lo, int hi, int x) {
if (hi >= lo && lo < arr.length - 1) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, lo, mid - 1, x);
return binarySearch(arr, mid + 1, hi, x);
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = {1, 2, 3, 4, 5};
int n = arr.length;
int x = 2;
int position = ob.binarySearch(arr, 0, n - 1, x);
if (position == -1)
System.out.println("Element not found !!!");
else
System.out.println("Element found at index: " + position);
}
}
出力：
Element found at index: 1
Arrays.binarySearch() 概要
Java はすぐに使える関数 Arrays.binarySearch() を提供してくれるので、自分で関数を実装する必要はありません。この関数は非常に使いやすく効率的に実装されており、エラーになることもありません。
構文
public static int binarySearch(T arr, T key)
T は以下のいずれかになります。int、float、short、long、byte、char、double, さらにはユーザ定義の Object を指定することもできます。
実装されている二分探索と同様に、配列をソートする必要があります。二分探索アルゴリズムを用いて配列を検索し、対象となる要素のインデックスを見つけます。対象となる要素が複数存在する場合は、そのうちのいずれかの要素のインデックスを返します。
パラメータ
Arr |
入力配列 |
Key |
検索対象の要素。 |
戻り値
対象となる要素が見つかった場合はそのインデックスを返します。それ以外の場合は beg - 1 を返します。ここで、beg は配列検索スペースの開始インデックスです。
二分探索のための Java プログラム
import java.util.Arrays;
class BinarySearchExample {
public static void main(String args[]) {
int arr[] = {1, 2, 3, 4, 5};
int key = 2;
int result = Arrays.binarySearch(arr, key);
if (result < 0)
System.out.println("Element is not found!");
else
System.out.println("Element is found at index: " + result);
}
}
出力：
Element is found at index: 1
