Java基本アルゴリズム——二分検索アルゴリズム
1428 ワード
にぶんたんさくアルゴリズム
検索するたびに配列の中位数の値を比較するターゲット値が中位数の値より大きい場合、中位数の右側の配列を切り取って再び二分検索を行い、ターゲット値が中位数の値より小さい場合、中位数の左側の配列を切り取って再び二分検索を行い、対応する中位数が見つかるまで検索アルゴリズムを終了します.つまり、比較するたびに検索範囲が半分に縮小されます.
whileサイクルによる二分検索
再帰的に二分検索アルゴリズムを実現する
mainメソッドで呼び出す
注意事項
検索する配列は、整列配列でなければなりません.
検索するたびに配列の中位数の値を比較するターゲット値が中位数の値より大きい場合、中位数の右側の配列を切り取って再び二分検索を行い、ターゲット値が中位数の値より小さい場合、中位数の左側の配列を切り取って再び二分検索を行い、対応する中位数が見つかるまで検索アルゴリズムを終了します.つまり、比較するたびに検索範囲が半分に縮小されます.
whileサイクルによる二分検索
private static int binSearch(int array[], int value){ int start=0;
int end =array.length-1;
int middle;
while(start<=end){
middle = (end-start)/2+start;
if(array[middle] < value){
start = middle+1;
}else if (array[middle]>value){
end = middle-1;
}else{
return middle;
}
}
return -1;
}
再帰的に二分検索アルゴリズムを実現する
private static int binSearch(int array[],int start,int end,int value){
int middle = (end-start)/2+start;
if(array[middle]==value){
return middle;
}
if(start>=end){
return -1;
} else if (array[middle]>value){
return binSearch(array,start,middle-1,value);
}else {
return binSearch(array,middle+1,end,value);
}
}
mainメソッドで呼び出す
public static void main(String[] args) {
int array[] ={1,2,3,4,5};
System.out.println("args = [" + binSearch(array,0,array.length-1,3) + "]");
}
注意事項
検索する配列は、整列配列でなければなりません.