黑马程序员技术交流社区

标题: 各位大神来看看 ，这为什么报错啊 [打印本页]

---

作者: 朱志江    时间: 2013-3-20 14:35
标题: 各位大神来看看 ，这为什么报错啊


折半查找法
给定一个数组{1,2,4,5,6,8,9,10}

class Shuzucz
{

        public static void main(String[] args)
        {
                int [] arr ={1,2,4,5,6,8,9,10};
                int position = binary(arr,11);
                System.out.println("position="+position);
        }

        public static int binary(int[] arr,int a)
        {
                int min,max,mid;
                        min=0;
                        max=arr.length;
                        mid=(min+max)/2;
                        
                while (arr[mid]!=a)
                {
                                if (a>arr[mid])
                                        min=mid+1;
                        else if(a<arr[mid])
                                        max=mid-1;

                        if (min>max)
                        return -1;

                        mid=(min+max)/2;
                }
                return min;

        }
}

为什么报错啊

QQ截图20130320143434.jpg (14.1 KB, 下载次数: 21)

下载附件

2013-3-20 14:34 上传

---

作者: 张亚青    时间: 2013-3-20 14:38


public static int binary(int[] arr,int a) 该方法中的 数组最大下标是 max=arr.length-1;


详细过程如下：（先按照楼主的做法运行）
数组为{1,2,4,5,6,8,9,10}

                                                      min        max        mid
第一次                                             0             8           4
第二次arr[4]=6<11   min=mid+1    5             8           6
第三次arr[6]=9<11   min=mid+1    7             8           7
第四次arr[7]=10<11 min=mid+1    8             8           8
这个时候min=mid=max=8，  代码中：if (min>max) return -1;
所以不会返回-1；
继续判断while (arr[mid]!=a)内的条件
但是

第五次arr[8] <------------到了这一步arr[8]不存在，所以报错！！！！
   

---

作者: 田磊阳    时间: 2013-3-20 14:42


java.lang.ArrayIndexOutOfBoundsException: 8

第8行数组越界了

max=arr.length;（这里是错误所在）,应该是max=arr.length-1;

输出结果为-1

纠错后的代码

class Demo
{
public static void main(String[] args)
    {
             int [] arr ={1,2,4,5,6,8,9,10};
             int position = binary(arr,11);
             System.out.println("position="+position);
     }
    public static int binary(int[] arr,int a)
     {
             int min,max,mid;
                     min=0;
                     max=arr.length-1;
                     mid=(min+max)/2;
                     
            while (arr[mid]!=a)
             {
                             if (a>arr[mid])
                                     min=mid+1;
                     else if(a<arr[mid])
                                     max=mid-1;
                    if (min>max)
                     return -1;
                    mid=(min+max)/2;
             }
             return min;
    }
}

---

作者: 孙宁    时间: 2013-3-20 14:43
                        int min,max,mid;
                        min=0;
                        max=arr.length;           //max=arr.length-1
                        mid=(min+max)/2;

---

作者: IT菜鸟    时间: 2013-3-20 15:31
数组下标是从0 开始的，而不是从1 开始的。所以max=arr.length-1 而不是max=arr.length

---

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

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