二分探索とは
線形探索では、目的とするキー値を持つ要素に出会うまで先頭から順に要素を走査していましたが、
そんな線形探索よりも高速に探索が行えるのが二分探索たるものらしいです。。
要素がキーの昇順または降順にソートされている配列から効率よく探索を行うアルゴリズム
とのことなので、探索対象となる配列は昇順・降順にソートされている必要があるみたいなので
配列だったら何でもかんでも使えるという訳ではなさそうです汗
具体的な探索手順としては、n個要素を持つ配列のちょうど中央に位置する(n-1/2)の要素を調べて、
探索対象よりも大きいか少ないかで、探索範囲を中央値よりも後か、前かに絞ると言った流れです。
(これ考えた人も頭ふにゃふにゃそう。。)
言葉で説明するのもあれなのでざっくりイメージで見てみましょう。
11個の要素が昇順で構成された配列があるとして、その中で5というキー値の位置を見つけたいとします。
11個の要素なので、まずは中央位置を(11-1)÷2
で求めます。(インデックスは0から始まるので、-1をしています)
すると間のインデックスは5と分かるので、5番目に位置している8の値とキー値を比較します。
5は8より小さく、中央値よりもキー値の方が小さいということになるので、先頭〜中央位置-1の間にキー値があるの絞ることができます。
これを繰り返し、最終的に間がなくなってしまったら探索失敗という判断ができます。
条件分岐とするなら下記の2つを繰り返していくイメージです。
- 中央値がキー値より大きければ左(中央値より大きい方)に絞り込む
- 中央値がキー値より小さければ右(中央値より小さい方)に絞り込む
イメージはなんとなくできたので、次にこの流れをコードに落とし込んでみましょう!
コードに落とし込んでみる
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
int array [] = new int[count];
array[0] = sc.nextInt();
for(int i = 1; i < count; i++){
do{
System.out.print("昇順で入力してください" + i +"番目の値: ");
array[i] = sc.nextInt();
// 入力された値が、一つ前の要素より大きくなるまで入力を繰り返す
}while (array[i - 1] > array[i]);
}
System.out.print("探す値: ");
int target = sc.nextInt();
int answer = search(array,count,target);
if(answer == -1){
System.out.println("探索失敗");
}else{
System.out.println(++answer +"番目に存在します");
}
}
public static int search(int [] array, int n, int key){
int start = 0; // 探索範囲開始インデックス
int end = n - 1; // 探索範囲末尾インデックス
do {
//中間インデックスを取得
int middle = (start + end) / 2;
//中間インデックスの値がキー値と一致していればキー値のインデックスを返す
if (array[middle] == key) {
return middle;
//キー値が中間値よりも大きければ、開始インデックスを中間より一つ後ろに設定(探索範囲を前半に分ける)
} else if (array[middle] < key) {
start = middle + 1;
//キー値が中間値よりも小さければ、末尾インデックスを中間より一つ前に設定(探索範囲を後半に分ける)
} else {
end = middle - 1;
}
//開始インデックスが末尾インデックス以上になれば超えてしまっているので終了
}while (start <= end);
return -1;
}
}
昇順で入力された数字で構成されたn個の配列から二分探索を使ってキー値の位置を求めています。
searchメソッドで実際に二分探索を行っていますが、条件分岐としては、キー値と一緒か、キー値の方が中央値より大きいか小さいかの3つとなります。
初期の探索範囲はインデックス的に 0 ~ n -1
となるので、この値を変えていくことで探索範囲を絞っています。
- 中央値がキー値より大きければ左(中央値より小さい方)に絞り込む → 中央位置から -1して後ろにする
- 中央値がキー値より小さければ右(中央値より大きい方)に絞り込む → 中央位置から +1して前にする
中央値を基準に探索範囲を前後に絞っていくという発想は凄いですよね。。
繰り返す分だけ、探索範囲が半分になっていくので、先頭から1つずつ要素をみていく線形探索よりも高速に行えるのは納得です。。
Arrays.binarySearchメソッド
先のように二分探索を自前で書くこともできるんですが、実はArraysクラスのメソッドとして既に定義されているみたいです。。
公式リファレンス
つまり、先ほどのsearchメソッドをそのまま1行で書けてしまうということですね、、
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
int array [] = new int[count];
array[0] = sc.nextInt();
for(int i = 1; i < count; i++){
do{
System.out.print("昇順で入力してください" + i +"番目の値: ");
array[i] = sc.nextInt();
// 入力された値が、一つ前の要素より大きくなるまで入力を繰り返す
}while (array[i - 1] > array[i]);
}
System.out.print("探す値: ");
int target = sc.nextInt();
//binarySearchメソッドを使って二分探索を実施
int answer = Arrays.binarySearch(array,target);
if(answer < 0){
System.out.println("探索失敗");
}else{
System.out.println(++answer +"番目に存在します");
}
}
}
これだけで終わりです、、昇順であれば基本的に扱えますが、Arraysクラスが提供しているメソッドで渡せる配列の型は下記になります。
byte,char,double,float,int.long,short,Object
あれ、Object型もいけるならほとんどのクラスはいけるやん!って話なんですが、このObject型の配列を渡せるメソッドのお陰で、Integer型やString型も扱うことができるんですね。。恐るべしbinarySearchメソッド。。
ちなみに、要素の大小関係は自然な順序で判定しているそうで、この自然な順序というと、整数や実数であれば、小さい方から大きい方へ、日付であれば古い方から新しい方へ、などと言った順序付けのことだそうです。
String型であってもObject型の配列として渡せるのはこれができるのは、ComparableというインターフェースをStringクラス内で実現しているとともに、compareToメソッドを実装しているからなんですね。。!
//Stringクラス
public int compareTo(String anotherString) {
byte[] v1 = this.value;
byte[] v2 = anotherString.value;
if (this.coder() == anotherString.coder()) {
return this.isLatin1() ? StringLatin1.compareTo(v1, v2) : StringUTF16.compareTo(v1, v2);
} else {
return this.isLatin1() ? StringLatin1.compareToUTF16(v1, v2) : StringUTF16.compareToLatin1(v1, v2);
}
}
//Integerクラス
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
細かいところまではみませんが、どちらも比較する2つの値を持ってきて、大小判定を行っています。
このように、compareToメソッドを実装しているクラスであれば、binarySearchメソッドの引数にObject型の配列として渡すことができるんですね!
自前のクラスでやってみる
String型とかInteger型とかでも使えるのは分かりましたが、実際のデータオブジェクトはデータの種類によってクラス分けされていることが多いですし、String型だけで構成されているデータ型というのもなかなかないと思います。
そんな自前のクラスでもbinarySearchを使いたいな、、となった場合に頼りになるのが下記メソッドです
public static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)
パッと見よく分かりませんが、これまでには存在しなかった第三引数にComaratorインターフェース方のインスタンスを渡していますね。。
実はbinarySearchメソッドが二分探索をするときには、昇順・降順に並んでいる配列の大小関係を判定する過程があり。。(ちょっと細かいところまでは分かっていません。。精進します。)自前のクラスで使用する場合は、何を以ってして大小とするのかをbinarySearchメソッドに通知する必要があるみたいです。
その通知方法というのが、この第三引数ということですね。。早速使ってみましょう。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//名前と身長を持つPhysicsDataのインスタンスで構成された配列を生成
PhysicsData [] people ={
new PhysicsData("BIM",163),
new PhysicsData("PUNPEE",175),
new PhysicsData("KREVA",187),
new PhysicsData("TOFUBEATS",191),
};
System.out.print("何cmの人を探していますか?: ");
int target = sc.nextInt();
int answer = Arrays.binarySearch(people,new PhysicsData("",target),PhysicsData.COMPARATOR);
if(answer < 0){
System.out.println("指定の身長の人はいません");
}else{
System.out.println("指定の身長の人は" + ++answer +"番目にいます");
}
}
}
public class PhysicsData{
private String name;
private int height;
public PhysicsData(String name, int height) {
this.name = name;
this.height = height;
}
public static final Comparator<PhysicsData> COMPARATOR = new HeightOrderComparator();
//Comparatorクラスを実現して、compareメソッドを実装
private static class HeightOrderComparator implements Comparator<PhysicsData>{
public int compare(PhysicsData a,PhysicsData b){
return (a.height > b.height)? 1 : (a.height < b.height)? -1 : 0;
}
}
}
名前と身長で構成されたPhysicsDataクラス
を要素に持つ配列から、入力した値の身長の人が何番目にいるかを
binarySearchメソッドを使って判定しています。
Arrays.binarySearch(people,new PhysicsData("",target),PhysicsData.COMPARATOR);
が実際にメソッドを使用している部分ですが、ここで第三引数で持ってきているPhysicsData.COMPARATOR
がPhysicsDataクラスにおける大小判定を表している部分です。
Comparatorインターフェースを実現しているHeightOrderComparatorクラス
にてcompareメソッドも実装しています。
public int compare(PhysicsData a,PhysicsData b){
return (a.height > b.height)? 1 : (a.height < b.height)? -1 : 0;
}
引数で渡さらた2つのPhysicsDataのインスタンスの内、前者の身長が大きければ1、後者の身長が大きければ -1
身長が同じであれば 0を返すようにしています。
このcompareメソッドの判定基準に基づいてbinarySearchメソッドが二分探索を行い、
キー値となる身長の人がいればそのインデックスを返すという実装が可能になるわけですね。。!
学んだこと
- 探索範囲を常に半分にする二分探索は線形探索よりも探索速度が早く、binarySearchメソッドで実装も可能
- 既にJavaのクラスにあるメソッドも中身を書いてみると理解が深まる
- Comparatorインターフェースは奥深いけど、もっと学びたい
学んだことに、もっと学びたいってって何だよ笑って感じですが、
正直Comparatorインターフェースの仕様はまだまだ分かっていない部分も多いので、今後も学びを深めていきたいです汗
また、今までであれば、binarySearchメソッドがよしなにやってくるのかとスルーしていた部分を二分探索という方法論から、
実際にコードに落とし込んでみることで、理解が深まった気がします!
深くいき過ぎる必要はなさそうですが、この "よしな" な部分を気にかけていく癖を付けていきたいです!
引き続き頑張っていきます!