- 递归实现
/**
* 递归实现二分查找算法
* @param array 有序数组
* @param num 要查找的元素
* @param start 起始下标
* @param end 结束下标
* @return 元素在有序数组中的下标
*/
public static int binarySearchByRecursion(int[] array, int num, int start, int end) {
if (start > end || array[start] > num || array[end] < num) {
return -1;
}
int mid = (start + end)/2;
if (num > array[mid]) {
return binarySearchByRecursion(array, num, mid + 1, end);
} else if (num < array[mid]) {
return binarySearchByRecursion(array, num, start, mid - 1);
} else {
return mid;
}
}
- 迭代实现
/**
* 迭代实现二分查找
* @param array 有序数组
* @param num 要查找的元素
* @return 元素在有序数组的下标
*/
public static int binarySearch(int[] array, int num) {
int start = 0;
int end = array.length - 1;
while (start < end) {
int mid = (start + end)/2;
if (num < array[mid]) {
end = mid - 1;
} else if (num > array[mid]) {
start = mid + 1;
} else {
return mid;
}
}
return -1;
}
