黑马程序员技术交流社区

标题: 自己写的折半查找算法出了点问题 [打印本页]
作者: 吴扬    时间: 2012-6-22 02:02
标题: 自己写的折半查找算法出了点问题
自己尝试着写了一下折半查找，但是还是出了问题，唉！很是郁闷...下面是我的代码：

  2. public class HalfSearch {
  3.         public static void main(String[] args) {
  4.                 int[] arr = {1, 3, 5 , 9, 12, 24, 30};
  5.                 System.out.println(halfSearch(arr, 2));
  6.         }
  7.         public static int halfSearch(int[] arr, int key)
  8.         {
  9.                 int min = 0;
  10.                 int max = arr.length-1;
  11.                 int mid = (min + max)/2;
  12.                
  13.                 while(arr[mid] != key)
  14.                 {       
  15.                         if(arr[mid] < key)
  16.                                 min = mid + 1;
  17.                         else if(arr[mid] > key)
  18.                                 max = mid - 1;
  19.                        
  20.                         else if(min > max)      //为什么这里如果是else if就会进入无限循环？
  21.                                 return -1;
  22.                         mid = (min+max)/2;
  23.                 }
  24.                 return mid;
  25.         }
  26. }
复制代码
问题出在带有注释的那行，我写的时候在if前面多加了个else，如果要查找的数据在数组中的话程序就能正常运行，但是如果要查找的数据不在数组中的话，程序就会进入死循环。
问题出在哪？求高手解答，先谢谢了！

作者: 余银桂    时间: 2012-6-22 02:07
本帖最后由 余银桂 于 2012-6-22 02:15 编辑
  1.                if(arr[mid] < key)

  3.                                 min = mid + 1;

  5.                         else if(arr[mid] > key)

  7.                                max = mid - 1;

  9.                         

  11.                         else if(min > max)      //为什么这里如果是else if就会进入无限循环？
  12.                                                         //很简单，这句判断是总的if判断的一个条件语句，当前面的有满足条件的，这句就当然永远执行不到了

  14.                                return -1;

  16.                       mid = (min+max)/2;
复制代码
顺道我在帮楼主改了一下代码，供参考！
  1.         public static void main(String[] args) {
  2.                
  3.                 int [] arr = {1,2,3,4,5,6,7,8,9};
  4.                 System.out.println( halfSearch(arr, 9) );
  5.                
  6.         }
  7.         public static int halfSearch( int[] arr,int key ){
  8.                
  9.                 int min = 0;
  10.                 int max = arr.length-1;
  11.                
  12.                 while( min <= max ){
  13.                         int mid = (min + max)/2;
  14.                         if( arr[mid] < key ){
  15.                                 min = mid + 1;
  16.                         }
  17.                         if( arr[mid] > key ){
  18.                                 max = mid - 1;
  19.                         }
  20.                         if( arr[mid] == key ){
  21.                                 return mid;
  22.                         }
  23.                        
  24.                 }
  25.                 return -1;
  26.                
  27.         }
复制代码
作者: 耿鑫    时间: 2012-6-22 02:25
本帖最后由 耿鑫 于 2012-6-22 02:42 编辑

你要查找的2在数组里根本就没有，你说它会不会一直找下去？？ 找一百年也找不到啊。

按代码来说，你在13行设个断点，然后用debug看一下，当执行几次循环之后你会发现min永远=1， max永远=0; mid永远=0; 然后arr[mid] = 1，永远arr[mid] < arr;
所以程序会不断的进入if(arr[mid] < key)，执行完 min = mid + 1;之后跳出if -else if - else if判断，到又去循环。不会执行到if(min > max)     return -1,所以不能跳出循环，这就是问题的原因。

如果去掉 写成 if(min > max)     return -1;的话就不会出现  if 和 if是两个判断体，if -else if - else if是一个判断体，一个条件满足后，就不会去判断其他的了。

                           

作者: 张华廷    时间: 2012-6-22 09:02
02.public class HalfSearch {

03.        public static void main(String[] args) {

04.                int[] arr = {1, 3, 5 , 9, 12, 24, 30};

05.                System.out.println(halfSearch(arr, 2));

06.        }

07.        public static int halfSearch(int[] arr, int key)

08.        {

09.                int min = 0;

10.                int max = arr.length-1;

11.                int mid = (min + max)/2;

12.               

13.                while(arr[mid] != key)

14.                {        

15.                        if(arr[mid] < key)

16.                                min = mid + 1;

17.                        else if(arr[mid] > key)

18.                                max = mid - 1;

19.                        

20.                        else if(min > max)      //语句在while循环内，满足条件执行return-1，不满足一直执行下去

21.                                return -1;

22.                        mid = (min+max)/2;

23.                }

24.                return mid;

25.        }

26.}

作者: 孙飞    时间: 2012-6-22 09:39
当你用的的else if时，它是上面if判断名的一个条件语句。按你写的来说，当arr[mid]=key时不进入while循环语句直接返回mid。当不等时，进入while循环语句，这时key要么满足arr[mid]<key，要么满足arr[mid]>key,即使min<max时key还是会要么满足arr[mid]<key，要么满足arr[mid]>key，所以就执行不到else if(min > max) 语句。就没有返回值，循环不会结束，就一直在那转着。如果把else if(min > max)中的else去掉，就成了while 中的另一条判断语句，当key不存在于数组中时，在上面的if语句中就会运行出min>max的结果，此时就会运行下面的if语句就会返回值来结束循环。这是折半查找，每次key在与a[mid]比较之后，都会判断key的位置是在a[mid]的左边还是右边，然后更改min或者max的值，然后继续判断。。这时候就要循环。。。所以mid=（min+max）/2；要放在循环里面，所以你while外面的那个mid=（min+max）/2只定义一下mid的类型就可以，不用赋值。
作者: 黑马_张佳超    时间: 2012-6-22 09:40
  1. public class HalfSearch {

  3.         public static void main(String[] args) {
  4.                 int[] arr = {1, 3, 5 , 9, 12, 24, 30};
  5.                 System.out.println(halfSearch(arr, 2));
  6.         }
  7.         public static int halfSearch(int[] arr, int key)
  8.         {
  9.                 int min = 0;
  10.                 int max = arr.length-1;
  11.                 int mid = (min + max)/2;
  12.                 while(arr[mid] != key)
  13.                 {        
  14.                         System.out.println(min+" "+max + " "+mid);
  15.                         if(arr[mid] < key && min <= mid-1)
  16.                                 min = mid + 1;
  17.                         else if(arr[mid] > key && max >= mid +1)
  18.                                 max = mid - 1;
  19.                         else if(min >= max)      //为什么这里如果是else if就会进入无限循环？
  20.                                 return -1;
  21.                         mid = (min+max)/2;
  22.                 }
  23.                 return mid;
  24.         }

  26. }
复制代码
else if(min >= max)      //为什么这里如果是else if就会进入无限循环？
else if 不是单独的if语句判断，他受其他if或者else if判断的影响。
假设一个if 后边还有一个else if ，如果if语句判断成立，程序就不会执行else if 中的判断里边的代码块。
你的程序判断的时候没有考虑到min与mid还有max与mid之间的大小添加到前几个判断语句中，导致程序永远执行不到最后的else if ，所以就产生了死循环。
你看看我帮你该的程序，判断条件如果完整了就不会导致无法执行最后一个else if 语句了。
当然，你也可以讲else if 语句拆分成独立的判断语句，这样的话就能执行到了。



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