一、二分查找法（二分折半查找）
1茶鹃、普通方法
/**
*@paramarr待查詢數(shù)組
*@paramfindValue待查詢值
*@return查詢值索引
*/
private static int binaryFind(int arr[], int findValue) {
//最小索引
int lowerBound = 0;
//最大索引
int upperBound = arr.length - 1;
//中間索引
int middleIndex;
//思想：1侄泽、當最小索引小于等于最大索引時
// 2懈贺、獲得middleIndex（中間索引）犀忱，以此判斷middleIndex對應(yīng)的值和findValue（查找值）是否對等
// 3、如果對等拜银，則返回當前索引殊鞭，否則改變最小和最大索引
// 4、不對等的情況尼桶，如果當前middleIndex對應(yīng)的值小于findValue操灿，則改變最小索引為middleIndex+1,否則改變最大索引為middleIndex-1
// 5、以此循環(huán)泵督，最終得到findValue的索引
while (lowerBound <= upperBound) {
middleIndex = (lowerBound + upperBound) / 2;
if (arr[middleIndex] == findValue) {
return middleIndex;
} else {
if (arr[middleIndex] < findValue) {
lowerBound = middleIndex + 1;
} else {
upperBound = middleIndex - 1;
}
}
}
return -1;
}
2牲尺、遞歸方法
/**
* 二分查找遞歸算法
* @param arr 待查詢數(shù)組
* @param currentValue 待查詢值
* @param beginIndex 起始索引
* @param endIndex 結(jié)束索引
* @return 查詢值索引
*/
private static int recursionBinaryFind(int[] arr, int currentValue, int beginIndex, int endIndex) {
if (beginIndex <= endIndex) {
int middleIndex = (beginIndex + endIndex) / 2;
//當查找值等于中間值時
if (currentValue == arr[middleIndex]) {
return middleIndex;
//當查找值大于中間值時，改變起始索引和結(jié)束索引，開始遞歸
} else if (arr[middleIndex] < currentValue) {
return recursionBinaryFind(arr, currentValue, middleIndex + 1, endIndex);
//當查找值小于中間值時谤碳，改變起始索引和結(jié)束索引，開始遞歸
} else{
return recursionBinaryFind(arr, currentValue, beginIndex, middleIndex - 1);
}
} else {
return -1;
}
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
