二分查找算法是一種在有序數(shù)組中查找某一特定元素的搜索算法顿膨。
搜素過程從數(shù)組的中間元素開始萤皂，如果中間元素正好是要查找的元素，則搜 素過程結(jié)束竭鞍；
如果某一特定元素大于或者小于中間元素板惑，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較偎快。
如果在某一步驟數(shù)組 為空冯乘，則代表找不到。
這種搜索算法每一次比較都使搜索范圍縮小一半晒夹。
折半搜索每次把搜索區(qū)域減少一半裆馒，時(shí)間復(fù)雜度為Ο(logn) 姊氓。
采用遞歸方式完成二分查找法
代碼：
public static int binSearch(int srcArray[], int start, int end, int key) {
int mid = (end - start) / 2 + start;
if (srcArray[mid] == key) {
return mid;
} if (start >= end) {
return -1;
} else if (key > srcArray[mid]) {
return binSearch(srcArray, mid + 1, end, key);
} else if (key < srcArray[mid]) {
return binSearch(srcArray, start, mid - 1, key);
}
return -1;
}
采用非遞歸方式完成二分查找法
代碼：
public static int binSearch(int srcArray[], int key) {
int mid = srcArray.length / 2;
if (key == srcArray[mid]) {
return mid;
}
int start = 0;
int end = srcArray.length - 1;
while (start <= end) {
mid = (end - start) / 2 + start;
if (key < srcArray[mid]) {
end = mid - 1;
} else if (key > srcArray[mid]) {
start = mid + 1;
} else {
return mid;
}
}
return -1;
}
