黑马程序员技术交流社区

标题: 折半查找 [打印本页]

---

作者: 赵学刚    时间: 2012-11-24 22:39
标题: 折半查找


public class test5 {
        
        public static int halfSearch(int b [],int key){
                int max=b.length-1,min=0,mid;
                while(min<=max){
                        mid=(max+min)>>1;
                        if(key>b[mid]){
                                mid=mid+1;
                        }else if(key<b[mid]){
                                max=mid-1;
                        }else{
                                return mid;
                        }
                        
                }
                return -1;
        }


        public static void main(String[] args) {

                int [] arr =new int[]{2,5,6,7,9,1};
               int index=halfSearch(arr,1);
                System.out.println("index="+index);
        }

}

为什么输出是-1呢，而key=2确实正确的结果，各位帮我看看哪里出问题了

---

作者: 赵学刚    时间: 2012-11-24 22:42
数组换成有序的还是不行

---

作者: 张学永    时间: 2012-11-24 22:47
if(key>b[mid]){
                                mid=mid+1;//这里写错了。。。。应该是min=mid+1
                        }else if(key<b[mid]){
                                max=mid-1;
                        }else{
                                return mid;
                        }

再有就是折半查找的前提是有序。

---

作者: 潘天功    时间: 2012-11-24 22:49
你代码写的不对，而且不规范，我把你的改了改，你看看吧
public static int halfSearch(int[] b,int key)
        {
                int min = 0;
                int max = b.length-1;
                int mid = (min+max)/2;

                while(b[mid]!=key)
                {
                        if(b[mid]>key)
                        {
                                max = mid - 1;
                        }
                        else if(b[mid]<key)
                        {
                                min = mid + 1;       
                        }
                        //如果小的索引比大的索引还大，那么，数据不存在。所以返回-1.
                        if(min>max)
                        {
                                return -1;
                        }


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

---

作者: 赵学刚    时间: 2012-11-24 23:10
嗯  谢谢

---

作者: 赵学刚    时间: 2012-12-3 00:19
问题已解决

---

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

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