欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}
}