二分探索を行うときに意外とインデックスエラーが発生するので、一旦ここで作ってまとめておきます。Comparableタイプに拡張しても良いですが、今回は整数型のみについて考えます。
目次
BinarySearchクラス
public class BinarySearch {
int size;
int[] arr;
...
}コンストラクタ
ソート済み配列を任意サイズにて生成します。
public BinarySearch(){
size = 10000;
arr = new int[size];
for (int i = 0;i<size;i++){
arr[i] = i;
}
}配列可視化
public String toString(){
String result = "[";
int i = 0;
while(i<size-1){
result += arr[i] +",";
i++;
}
return result+arr[i] +"]";
}サーチメソッド
左右の可変インデックスを使用してターゲットを探索します。
public int search(int target){
if (target>arr[size-1]){
return -1;
}
int left = 0;
int right = size-1;
int m = (left+right)/2;
while(target != arr[m]){
if (target<arr[m]){
right = m;
m = (left+right)/2;
}else{
left = m;
m = (left+right)/2+1;
}
}
return m;
}Searchテスト
配列内の全要素について二分探索を行い、インデックスエラーがないかどうかを念のため確認します。
public static void main(String[] args) {
BinarySearch b = new BinarySearch();
System.out.println(b.size);
for (int i = 0;i<b.size;i++){
System.out.println(b.search(i));
}
}
