额 我感觉不需要说什么的,递归本就需要点想象吧~
package 递归基础小题;
import java.util.Scanner;
/**
* @author 邓雪松 (づ ̄ 3 ̄)づ)
* @create 2021-10-25-19-06
*/
public class 二分查找递归解法 {
public static void main(String[] args) {
int arr[] = {1,3,2,4,5,6,8};
System.out.println("请输入你想查找的整数(1-10):");
Scanner scanner = new Scanner(System.in);
int x = scanner.nextInt();
int y = binarySearch1(arr,0,arr.length,x);
if(y==-1){
System.out.println("查无此数~");
}else{
System.out.println("查有此数~");
}
}
//递归解法
private static int binarySearch1(int[] arr,int low,int high,int key){
if(low>high)
return -1;//没找到
int mid = low + ((high-low)>>1);//(low+high)>>>1;//防止溢出,移位也更高效
int midVal = arr[mid];
if(midVal<key)
return binarySearch1(arr,mid+1,high,key);
else if(midVal>key)
return binarySearch1(arr,low,high-1,key);
else
return mid;//key found
}
}
运行结果如下
请输入你想查找的整数(1-10):
7
查无此数~