黑马程序员技术交流社区

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

---

作者: 竹叶君子    时间: 2015-3-1 13:25
标题: 折半查找

1. class Test1
   
2. {
   
3.    public static void main(String[] args)
   
4.    {
   
5.      int[] arr={1,2,3,4,5,6,7,8,9,10};
   
6.      int key=8;
   
7.      int n= halfSearch(arr,key);
   
8. System.out.println("毕向东老师的代码结果"+n);

复制代码

这个是折半查找的代码，我练习的时候把min=mid+1写成了min=mid、min=mid-1写成了max=mid，在编译运行的时候发现也能得出相同的结果，各位大神帮我看看是什么情况？

---

作者: 竹叶君子    时间: 2015-3-1 13:27
class Test1
{
   public static void main(String[] args)
   {
     int[] arr={1,2,3,4,5,6,7,8,9,12};
     int key=8;
     int n= halfSearch(arr,key);
     int m=halfSearch_1(arr,key);
     System.out.println("毕向东老师的代码结果"+n);
     System.out.println("减1后的结果"+m);
   }
   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)
                                return -1;
                        mid = (max+min)/2;
                }
                return mid;
        }

//修改后的折半查找函数
public static int halfSearch_1(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;    //把min=mid+1改为min=mid
                        else if(key<arr[mid])
                                max = mid;     //把min=mid-1改为max=mid

                        if(min>max)
                                return -1;
                        mid = (max+min)/2;
                }
                return mid;
        }

}

---

作者: wdhm5423    时间: 2015-3-1 13:33


逻辑问题
min=mid+1，表示从mid+1到max继续找。你写成了min=mid，从mid到max继续找，当然也是可以的，照样能找到。不过mid既然已经不是了，最好还是从mid+1开始找。
max=mid-1，表示从min到mid-1继续找。你写成了max=mid，从min到mid继续找，当然也是可以的，照样能找到。不过mid既然已经不是了，最好还是从min找到mid-1就行了。

---

作者: zhaohe513    时间: 2015-3-1 13:47
好来看看学习一下

---

作者: 竹叶君子    时间: 2015-3-2 09:14
我找到问题原因了，不能把min=mid+1写成min=mid、也不能把min=mid-1写成max=mid。
因为当把min=mid+1写成min=mid、把min=mid-1写成max=mid后，如果key的值为最后一个数话，运行就始终找不到结果，程序就会陷入死循环中。例如，在本例中，key=12，那么最终的结果是min=8，max=9，mid=8，程序会一直拿角标为8的数和key的值进行比较，从而陷入死循环中。

---

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

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