黑马程序员技术交流社区

标题: Java数组折半排序问题？新人求解答 [打印本页]

---

作者: anyway1919    时间: 2015-7-24 16:37
标题: Java数组折半排序问题？新人求解答
//今天看了毕向东老师的Java基础视屏，有点问题不清楚。请大家帮忙看看，谢谢！
class ArrayTest
{
        public static void main(String[] args)
        {

                int [] arr = new int[]{1,3,4,6,8,9,12};
                int index = halfSearch(arr,30);
                System.out.println("index="+index);//返回数组角标值
               
        }

        /*
        折半查找。
        */
        public static int halfSearch(int[] arr,int key)
        {
                int min,max,mid;
                min = 0;
                max = arr.length-1;
                mid = (max+min)/2;

                while(arr[mid]!=key)
                {
                        if(key>arr[mid])
                                min = mid +1;
                        else if (key<arr[mid])
                       
                                max = mid-1;
                       
                        if (min>max)//<<<<------问题就在这，为什么用min>max该判断能够判定key在数组中不存在呢？
                       
                                return -1;
                       
                        mid = (max+min)/2;
                  }
                return mid;
        }
       
}

---

作者: softzhang    时间: 2015-7-24 18:13
其实你只要在代码中加入这两句输出语句就很明白


30超过整个数组最大值，所以会执行if(key>arr[mid])里面min = mid +1;语句，这时候min相对应变化了
再执行if (min>max)不成立继续执行mid = (max+min)/2;，mid相对应变化了。
再次执行循环体又执行if(key>arr[mid])里面min = mid +1;再执行if (min>max)不成立；执行mid = (max+min)/2；每次min和max都往上一轮的后面一部分变化。当min循环累加到和max一样大之后，if(key>arr[mid])依旧成立，也就是key比最大值还大，再执行min = mid +1;那么执行if (min>max)成立了，就返回-1，跳出循环了，你看图就很明白的。
其实查找数组范围之类但是不存在的整数也是同样的方法返回-1.

---

作者: anyway1919    时间: 2015-7-24 18:50

softzhang 发表于 2015-7-24 18:13
其实你只要在代码中加入这两句输出语句就很明白

谢谢你的超详细的回答。经过你的点播，理解的深些。。感觉自己循环结构还没有很熟悉掌握

---

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

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