黑马程序员技术交流社区

标题: 我的二分查找的一个错误代码，怎么改 [打印本页]

---

作者: 江大海    时间: 2013-4-19 07:57
标题: 我的二分查找的一个错误代码，怎么改
这个是我写的一个二分查找，编译通过，为什么会说是角标越界异常呢？我写了if (min>max)语句啊，和老师写的对比了半天也不知道为什么，求帮助

1. /*二分查找
   
2. */
   
3. 
   
4. class ArrDemo_2
   
5. {
   
6.         public static void main(String[] args)
   
7.         {
   
8.                 int [] arr ={1,2,3,4,5,6};
   
9.                 halfSearch(arr,31);
   
10.                
    
11.         }
    
12.         public static void halfSearch(int [] arr,int key)
    
13.         {
    
14.                 int min = 0,max = arr.length,mid;
    
15.                 mid = (min +max)/2;
    
16.                 while (arr[mid]!=key)
    
17.                 {
    
18.                        
    
19.                  if (arr[mid]>key)
    
20.                         {
    
21.                                 max = mid-1;
    
22.                                 mid = (min +max)/2;
    
23.                         }
    
24.                         else if (arr[mid]<key)
    
25.                         {
    
26.                                 min = mid+1;
    
27.                         mid = (min +max)/2;
    
28.                         }
    
29.                        
    
30.                         if (min>max)
    
31.                         mid=-1;
    
32.                
    
33.                        
    
34.                 }
    
35.                 System.out.println(mid);
    
36.         }
    
37. }
    

复制代码

---

作者: 贺靖轩    时间: 2013-4-19 08:34
14行：int min = 0,max = arr.length,mid;
min既然定义成0，与第一个元素对应，
那max应该为arr.length-1，下标为arr.length的元素不存在，当然会越界。

---

作者: Just_Only    时间: 2013-4-19 08:37
int min = 0,max = arr.length,mid;
你这里的max所取的值越界了，应该是max=arr.length-1,数组的长度是arr.length但是能取的下标却是arr.length-1，因为数组的下标是从零开始的。

---

作者: 心弦上的景致    时间: 2013-4-19 08:40

1. 
   
2. //   整形数组长度是六
   
3. 08.                int [] arr ={1,2,3,4,5,6};
   
4. //   传31 就出问题了
   
5. 09.                halfSearch(arr,31);
   

复制代码

java.lang.ArrayIndexOutOfBoundsException  ： 这个异常是数组角标越界异常

---

作者: 汪平乐    时间: 2013-4-19 08:47
int min = 0,max = arr.length,mid; //元素有arr.length个，但元素的坐标是0——arr.length-1
另外折半查找中我想问是：
mid = (min +max)/2;
  mid = (min +max)>>1;的速度快点？

---

作者: 黑马伍哲沂    时间: 2013-4-19 09:05


这个代码里有三个问题：
第一，max应该是length-1；
第二，循环条件，应该要改，有两种该法，⑴改为while（min<max），如果这么改，则mid=（min+max）/2或者mid=（min+max）>>1只能在判断之前，即在循环内第一条语句。⑵改为while（min<=max），则后面的可以不改。
第三，第30行，if，用else即可。
我用两种方法修改后的程序如下供参考（注：我用的是带返回值的，返回角标更合理）：

1. public static int halfSearch(int [] arr,int key)
   
2.         {
   
3.                         int min = 0,max = arr.length-1,mid=(min+max)/2;
   
4.                         while (min <= max)         
   
5.                         {
   
6. //                                mid = (min +max)/2;
   
7.                                        
   
8.                                 if (arr[mid]>key)
   
9.                                 {
   
10.                                         max = mid-1;
    
11.                                         mid = (min +max)/2;
    
12.                                 }
    
13.                                 else if (arr[mid]<key)
    
14.                                 {
    
15.                                         min = mid+1;
    
16.                                         mid = (min +max)/2;
    
17.                                 }
    
18.                                                 
    
19.                                 else
    
20.                                         return mid;
    
21.                         }
    
22.                         return -1;
    
23. 
    
24.         }

复制代码

或者

1. public static int halfSearch(int [] arr,int key)
   
2.         {
   
3.                         int min = 0,max = arr.length-1,mid=(min+max)/2;
   
4.                         while (min < max)
   
5.                         {
   
6.                                 mid = (min +max)/2;
   
7.                                        
   
8.                                 if (arr[mid]>key)
   
9.                                 {
   
10.                                         max = mid-1;
    
11.                                         //mid = (min +max)/2;
    
12.                                 }
    
13.                                 else if (arr[mid]<key)
    
14.                                 {
    
15.                                         min = mid+1;
    
16.                                         //mid = (min +max)/2;
    
17.                                 }
    
18.                                                 
    
19.                                 else
    
20.                                         return mid;
    
21.                         }
    
22.                         return -1;
    
23. 
    
24.         }

复制代码

---

作者: yufeng47    时间: 2013-4-19 09:23

1. int [] arr ={1,2,3,4,5,6};
   
2. nt min = 0,max = arr.length,mid;
   

复制代码

错误在：max = arr.length,应该为，max = arr.length-1。
分析哈角标的移动：
C:\Documents and Settings\Administrator\桌面\1.JPG

1.JPG (66.79 KB, 下载次数: 10)

下载附件

2013-4-19 09:22 上传

---

作者: 刘印12    时间: 2013-4-19 11:03

1. /*二分查找
   
2. */
   
3. 
   
4. class ArrDemo_2
   
5. {
   
6. public static void main(String[] args)
   
7. {
   
8. int [] arr ={1,2,3,4,5,6};
   
9. halfSearch(arr,31);
   
10. 
    
11. }
    
12. public static void halfSearch(int [] arr,int key)
    
13. {
    
14. int min = 0,max = arr.length,mid;
    
15. mid = (min +max)/2;
    
16. while (arr[mid]!=key)
    
17. {
    
18. 
    
19. if (arr[mid]>key)
    
20. {
    
21. max = mid-1;
    
22. mid = (min +max)/2;
    
23. }
    
24. else if (arr[mid]<key)
    
25. {
    
26. min = mid+1;
    
27. mid = (min +max)/2;
    
28. }
    
29. 
    
30. if (min>max)
    
31. mid=-1;
    
32. 
    
33. 
    
34. }
    
35. System.out.println(mid);
    
36. }
    
37. }

复制代码

报错的地方是十四行，你定义max的时候max的最大角标应该是arr。length-1.因为你传递的数组长度是6 而最大角标值是5

---

作者: 梁志兵    时间: 2013-4-19 22:50
你的代码没有错


class ArrDemo_2

{

        public static void main(String[] args)

        {

                int [] arr ={1,2,3,4,5,6};

                halfSearch(arr,31);//是你在这里定义的31出了问题，是因为你定义  int [] arr ={1,2,3,4,5,6};没有31这个数，你可以传个3试试



               

        }

        public static void halfSearch(int [] arr,int key)

        {

                int min = 0,max = arr.length,mid;

                mid = (min +max)/2;

                while (arr[mid]!=key)

                {

                        

                 if (arr[mid]>key)

                        {

                                max = mid-1;

                                mid = (min +max)/2;

                        }

                        else if (arr[mid]<key)

                        {

                                min = mid+1;

                        mid = (min +max)/2;

                        }

                        

                        if (min>max)

                        mid=-1;

               

                        

                }

                System.out.println(mid);

        }

}

---

作者: 江大海    时间: 2013-4-21 19:30
soga.知道了，谢谢啦

---

作者: 江大海    时间: 2013-4-21 19:32

梁志兵 发表于 2013-4-19 22:50
你的代码没有错

是错啦，我也知道传3没有错，但是传的31的话就会出错，因为这也是一种查找的情况啊，就像上面的朋友说的，是我的max取错了。谢谢啦

---

作者: 江大海    时间: 2013-4-21 19:32

刘印12 发表于 2013-4-19 11:03
报错的地方是十四行，你定义max的时候max的最大角标应该是arr。length-1.因为你传递的数组长度是6 而最大角 ...

恩，知道啦，谢谢

---

作者: 江大海    时间: 2013-4-21 19:32

yufeng47 发表于 2013-4-19 09:23
错误在：max = arr.length,应该为，max = arr.length-1。
分析哈角标的移动：

恩，知道啦，谢谢

---

作者: 江大海    时间: 2013-4-21 19:33

黑马伍哲沂 发表于 2013-4-19 09:05
这个代码里有三个问题：
第一，max应该是length-1；
第二，循环条件，应该要改，有两种该法，⑴改为while（ ...

恩，知道啦，谢谢

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2