黑马程序员技术交流社区

标题: 折半查找问题 [打印本页]
作者: 彭刚    时间: 2013-12-4 09:39
标题: 折半查找问题
如题，一下代码结果为什么不是-1而是角标越界，key应该是元素值啊
class  ArrayTest4
{
    public static void main(String[] args)
        {
               int[] arr ={1,2,3,4,5,6};
           int index = halfSearch_1(arr,10);
           System.out.println("index="+index);
    }
    public static int halfSearch_1(int[] arr, int key)
        {
                int Max=arr.length, Min=0, Mid;
                while (Min<=Max)
                {
                        Mid =(Min+Max)>>1;
                        if (key>arr[Mid])
                                Min = Mid + 1;
                        else if (key<arr[Mid])
                                Max = Mid - 1;
                        else
                                return Mid;
                }
                return -1;
     }
}
作者: ❦_H_t    时间: 2013-12-4 10:00
arr.length代表是的数组长度,而数组角标是从0开始的,所以你代码中int Max=arr.length应该改为int Max=arr.length-1,如果是int Max=arr.length当然会出现角标越界异常了。
作者: 李文帅    时间: 2013-12-4 10:05
楼主的程序有问题：变量max初始化时应该是最大元素的下标，应该是arr.length-1
应该把代码'max = arr.length'改为'max = arr.length-1'
至于报下标越界异常是因为
当传递的key值大于数组中的最大值时，max的值不会改变，为arr.length，min的值一直会变大，
循环到最后min=max=arr.length'，此时mid=arr.length，而数组最大下标为arr.length-1'，
所以当程序执行到if (key>arr[mid])时，会发生数组下标越界异常
作者: 彭刚    时间: 2013-12-4 10:11
非常感谢
作者: ily521125    时间: 2013-12-4 12:49
正确代码如下：

  2. <P>class  ArrayTest
  3. {
  4.     public static void main(String[] args)
  5.         {
  6.                int[] arr ={1,2,3,4,5,6};
  7.            int index = halfSearch_1(arr,10);
  8.            System.out.println("index="+index);
  9.     }
  10.     public static int halfSearch_1(int[] arr, int key)
  11.         {
  12.                 int Max=arr.length-1, Min=0, Mid;
  13.                 while (Min<=Max)
  14.                 {
  15.                         Mid =(Min+Max)>>1;
  16.                         if (key>arr[Mid])
  17.                                 Min = Mid + 1;
  18.                         else if (key<arr[Mid])
  19.                                 Max = Mid - 1;
  20.                         else
  21.                                 return Mid;
  22.                 }
  23.                 return -1;
  24.      }
  25. }</P>
复制代码

作者: 简★零度    时间: 2013-12-5 22:54
下次问题解决了就把类型改成提问结束！谢谢!



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