作者:菠萝和尚 | 来源:互联网 | 2023-06-02 11:04
二分查找常见的都是递归的实现形式,这里实现了一种非递归的二分查找:importjava.util.Scanner;publicclassBinarySearchNonRecursively{p
二分查找常见的都是递归的实现形式,这里实现了一种非递归的二分查找:
import java.util.Scanner;
public class BinarySearchNonRecursively {
public static int binarySearch( int length, int[] array, int start, int end, int key){
//判断输入是否合法
if (array == null || start <0 || end <0 || end array[end]){
return -1;
}
int middle = (start+end)/2;
//判断初始middle位置值是否为要查找的值
if (array[middle] == key){
return middle;
}
else{
//开始循环
while (array[middle] != key){
//如果新的一轮循环开始时,start处值大于要查找值或end处值小于要查找值,说明要查找的值不在数组中
if (array[start]>key || array[end]return -1;
}
else if (array[middle] > key){
end = middle-1;
}
else{
start = middle+1;
}
middle = (start+end)/2;
}
return middle;
}
}
public static void main(String[] args){
Scanner sc1 = new Scanner(System.in);
System.out.println("Please input the length of the array:");
int length = sc1.nextInt();
System.out.println("Please input the array:");
int[] a = new int[length];
for (int i=0; ia[i] = sc1.nextInt();
}
System.out.println("Please input the key:");
int key = sc1.nextInt();
sc1.close();
System.out.print(binarySearch(length, a, 0, length-1, key));
}
}