二分法查找的实现【java实现二分法查找】
发布于 2021-10-31 05:36:18
浏览 165
详情：
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、
}
上一篇：Creo如何创建骨架模型
下一篇：历届世界杯金球奖得主都有哪些
