二分法查找的实现【java实现二分法查找】

发布于 2021-10-31 05:36:18 浏览 264 次

前述

详情

问题解析：

【】

1、 1.理清思路：首先得明确最简单的基础，就是如何实现二分法查找，很简单的想到的是取中间值，比较要查找的值，查找对象。我们可以先创建一个类，进行简单的处理。如下图： 2、 class find{ 3、 public int Dicfind(int min,int max,int a[],int value){ 4、 return value;} 5、 } 6、 2.定义一个类，然后写一个方法来接收一个数组的下标和要查找的值，二分法首先是对中间那个数和要查找的数进行比较，即有 7、 class find{ 8、 public int Dicfind(int min,int max,int a[],int value){ 9、 int mid=(min+max)/2; 10、 //比较a[mid]和value 11、 if(a[mid]>value){ 12、 } 13、 return value; 14、 } 15、 } 16、 3.现在就是思考的难点来了，如何分析并继续下一步查找问题，例如给你一组数据a[]={1,2,4,5,6};查找的值为2，第一次查找mid=2;a[2]>2;那么如何进行下一步查找呢，这里我们使用递归调用，这就是为什么我们要设置方法返回类型为int的原因（实现递归）。代码如下： 17、 class find{ 18、 public int Dicfind(int min,int max,int a[],int value){ 19、 int mid=(min+max)/2; 20、 int i=0; 21、 //比较a[mid]和value 22、 if(a[mid]>value){ 23、 return Dicfind(min,mid-1,a,value); 24、 } 25、 return value; 26、 } 27、 } 28、 4.同理进行a[mid]<value;a[mid]>value;a[mid]=value的出理，具体代码如下： 29、 class find{ 30、 public int Dicfind(int min,int max,int a[],int value){ 31、 int mid=(min+max)/2; 32、 //比较a[mid]和value 33、 if(a[mid]>value){ 34、 return Dicfind(min,mid-1,a,value); 35、 } if(a[mid]<value){ 36、 return Dicfind(mid+1,max,a,value); 37、 } 38、 if(a[mid]==value){ 39、 System.out.println("查到这个数了：是第"+(mid+1)+"数"); 40、 } 41、 return value; 42、 } 43、 } 44、 5.然后在main方法中测试一下，具体代码如下，为了方便调用我们把方法写出静态的，方便使用。执行看到效果（下图所示）！具体代码如下： 45、 package demo2; 46、 public class Test { 47、 public static void main(String[] args) { 48、 // TODO Auto-generated method stub 49、 int[] a={1,2,3,4,5}; 50、 find.Dicfind(0, a.length-1, a, 2); 51、 } 52、 } 53、 class find{ 54、 public static int Dicfind(int min,int max,int a[],int value){ 55、 int mid=(min+max)/2; 56、 //比较a[mid]和value 57、 if(a[mid]>value){ 58、 return Dicfind(min,mid-1,a,value); 59、 } if(a[mid]<value){ 60、 return Dicfind(mid+1,max,a,value); 61、 } 62、 if(a[mid]==value){ 63、 System.out.println("查到这个数了：是第"+(mid+1)+"数"); 64、 } 65、 return -2; 66、 } 67、 } 68、 6.如果你觉得这就算完成了二分法查找这个例子的话，那你就还需要思考更多。比如，如果没有这个数怎么办，你可以在上面那个代码中测试，然后寻找问题。以下是本人思考后，对简单二分法查找数组元素的优化代码。仅供参考！ 69、 package demo2; 70、 public class Test { 71、 public static void main(String[] args) { 72、 // TODO Auto-generated method stub 73、 int[] a={1,3,4,5}; 74、 for(int i=0;i<6;i++){ 75、 System.out.println("查找的数字"+i); 76、 find.Dicfind(0, a.length-1, a, i); 77、 } 78、 } 79、 } 80、 class find{ 81、 public static int Dicfind(int min,int max,int a[],int value){ 82、 if(a[0]>value||a[max]<value){ 83、 System.out.println("没有这个数！"); 84、 }else{ 85、 int mid=(min+max)/2; 86、 //比较a[mid]和value 87、 if(a[mid]>value){ 88、 return Dicfind(min,mid-1,a,value); 89、 } if(a[mid]<value){ 90、 return Dicfind(mid+1,max,a,value); 91、 } 92、 if(a[mid]==value){ 93、 System.out.println("查到这个数了：是第"+(mid+1)+"数"); 94、 }else return value;} 95、 return value; 96、 } 97、 }