Java实现二分查找(递归与非递归)
程序员文章站
2022-03-14 20:36:51
...
前提条件:使用二分查找的数组必须是有序的。
public class BinarySearch {
public static void main(String[] args) {
int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 9, 10 };
System.out.println(search1(array, 0, array.length - 1, 10));
System.out.println(search2(array, 10));
}
/**
* 递归写法
*
* @param array
* @param low
* @param high
* @param value
* @return int
*/
public static int search1(int[] array, int low, int high, int value) {
int mid = (low + high) / 2;
if (array[mid] == value) {
return mid;
} else if (array[mid] < value) {
return search1(array, mid + 1, high, value);
} else {
return search1(array, 0, mid - 1, value);
}
}
/**
* 非递归写法
*
* @param array
* @param value
* @return int
*/
public static int search2(int[] array, int value) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (array[mid] == value) {
return mid;
} else if (array[mid] < value) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}
上一篇: 在css样式中class是什么
下一篇: UVa 712 S树(S-Trees)