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