二分查找java完整算法
假设我们在词典中查找一个k开头的单词，我们会怎么做呢？ 1. 从词典第一页开始一页一页的翻页，然后直到翻到k开头的单词。 2. 直接翻页到词典大概中间的位置，然后根据词典a-z排列规律，判断翻到的页在k之前，还是之后，然后继续翻页。
其实这就是一个查找问题，上面第二种方法就是 二分查找
我们再举一个例子： 我自己随便想一个 1-100 之间的数字，然后让你来猜，你每次猜测之后我都会告诉你，猜大了还是猜小了。（假设我心中想的数字是60）
- 第一种方式：假设你从
1开始依次往上猜，要猜到60你得猜60次才能猜到。这种方式就是简单查找。（当然聪明如你肯定不会以这种方式来猜） - 第二种方式：从
50开始，小了，排除1-50，排除了一半数字；接下来你猜75，大了，又排除了一半数字75-100；接下来你猜63，大了；依次类推，你每次猜测的都是中间的数字，从而每次都将余下的数字排除一半，无论我心中的所想的数字是几，你在7步之内就能猜到。（大家想想为什么是7次？给个提示，2的6次方是64,2的7次方是128。）
上述第二种方式就是 二分查找 。
一般而言，对于包含n个元素的列表，用二分查找最多需要 logn 步（log以2为底），用简单查找最多需要 n 步
接下来我们看看如何编写二分查找的Java代码，有两种方式，一种是利用循环，另一种是利用递归
https://baijiahao.baidu.com/s?id=1647644071864997557&wfr=spider&for=pc
另外需要注意的是，二分查找只能应用在排好顺序的数组或列表上。int[] array = {1,4,8,16,45,48,78};这个就是顺序拍好的
非递归方式：由于辅助空间是常数级别的所以：空间复杂度是O(1);
递归方式：递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：空间复杂度：O(log2N )。
第一种：循环
package find;
import java.util.Scanner;
//适用场景：顺序存储结构且按有序排列，这也是它的缺点。
public class erfen {
public static void main(String[] args) {
int[] array = {1,4,8,16,45,48,78};
System.out.println("请输入想要查找的数值：");
Scanner sc=new Scanner(System.in);
int key=sc.nextInt();
int s=binSearch_1(key,array);
if(s==-1){
System.out.println("没有这个数据");
}else{
System.out.println("查到数据下标为"+s);
System.out.println("查到数据为第"+(s+1)+"个数");
}
}
//循环实现二分算法
public static int binSearch_1(int key,int array[]){
int low=0;//第一个下标
int height=array.length-1;//最后一个下标
int middle=0;
//防越界
if (key<array[low] || key>array[height]||low>height){
return -1;
}
//因为是顺序有序排列，所以我们可以用key和middle比较
while(low<=height){
middle=(low+height)/2;
if(array[middle]>key){
//比要查找的关键字大则关键字在中间值左边
height=middle-1;
}else if(array[middle]<key){
//比要查找的关键字小则关键字在中间值右边
low=middle+1;
}else{
return middle;
}
}
return -1;//最后什么没找到返回-1
}
}第二种：递归
package find;
import java.util.Scanner;
public class erfen2 {public static void main(String[] args) {
int[] array = {1,4,8,16,45,48,78};
System.out.println("请输入想要查找的数值：");
Scanner sc=new Scanner(System.in);
int key=sc.nextInt();
int low=0;
int high=array.length-1;
int s=binSearch_2(array,key,low,high);
if(s==-1){
System.out.println("没有这个数据");
}else{
System.out.println("查到数据下标为"+s);
System.out.println("查到数据为第"+(s+1)+"个数");
}
}
//递归实现二分算法
public static int binSearch_2(int[] arr,int key,int low,int high){
if(key < arr[low] || key > arr[high] || low > high){
return -1;
}
int middle = (low + high) / 2; //初始中间位置
if(arr[middle] > key){
//比关键字大则关键字在左区域
return binSearch_2(arr, key,low,middle-1);
}else if(arr[middle] < key){
//比关键字小则关键字在右区域
return binSearch_2(arr, key,middle+1,high);
}else {
return middle;
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读