目的のデータを探索する探索法が二分探索法です。
二分探索法は、探索前に配列のデータをソートする必要があります。
中央のデータを除き、探索範囲を縮小して探索をします。
public class Example4 {
public static void main(String[] args) {
int[] num = { 5, 30, 10, 20, 70, 90 };
Arrays.sort(num);
System.out.println(Arrays.toString(num)); //ソートした配列を出力
System.out.println("インデックス：" + search(num, 30));
}
public static int search(int[] data, int target) {
int result = -1;
int left = 0; //配列のインデックスは0から始まるから左端は0
int right = data.length - 1; //右端はインデックスが要素-1になるから
while(left <= right) {
int middle = (left + right) / 2; //中央のデータを求める
if(data[middle] == target) {
return middle;
}else if(data[middle] < target) {
left = middle + 1;
}else {
right = middle - 1;
}
}
return result;
}
}
===== 実行結果 =====
[5, 10, 20, 30, 70, 90]
インデックス：4
====================
中央のデータと目的のデータが一致した場合は、中央の値をreturn。
目的のデータが大きい場合は「middle + 1」して探索範囲を縮小。
目的のデータが小さい場合は「middle - 1」して探索範囲を縮小。
「0,1,2,3,4,5,6」
中央が「3」だとします。「3」を基準として大小関係を調べて
目的のデータが中央のデータと同じ場合は「return 3」。
目的のデータが大きい場合、0〜3には目的のデータは存在しない。
なので、探索範囲を縮小するために
中央のデータに+1して中央のデータを除いた4〜6を探索します。
この時、新たに「int middle = (left + right) / 2」で
中央のデータが設定されます。
大きい場合だと、4〜6に探索範囲が縮小されると
中央の値は「(4 + 6) / 2」で5になります。
逆に、目的のデータが小さい場合、3〜6には目的のデータは存在しない。
なので、探索範囲を縮小するために
中央のデータに-1して中央のデータを除いた0〜2を探索します。
この時、新たに「int middle = (left + right) / 2」で
中央のデータが設定されます。
小さい場合だと、0〜2に探索範囲が縮小されると
中央の値は「(0 + 2) / 2」で1になります。
最後に、int型となっているので少数点以下は切り捨てられます。
APIで用意されているメソッドを使用した二分探索もあります。
それは、また次回に。
† 地球の末路！？ †
【このカテゴリーの最新記事】
- no image
-
-
-
- no image
