黑马程序员技术交流社区

标题: 关于折半查找的问题 [打印本页]
作者: rolling-stone    时间: 2014-7-31 18:02
标题: 关于折半查找的问题
  1. class  SzDemo5
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 int[] arr = {4,2,1,8,4,6};
  6.                 Show(arr);
  7.                 PX(arr);
  8.                 Show(arr);
  9.                 System.out.println("arr["+Find(arr,8)+"]");
  10.         }
  11.         public static void PX(int[] arr)
  12.         {
  13.                 for(int i=0; i<arr.length; i++)
  14.                 {
  15.                         for(int j=0; j<arr.length-1; j++)
  16.                         {
  17.                                 if(arr[j]>arr[j+1])
  18.                                 {
  19.                                         Swap(arr,j,j+1);
  20.                                 }
  21.                         }
  22.                 }
  23.         }
  24.         public static int Find(int[] arr, int key)
  25.         {
  26.                 int max = arr.length-1;
  27.                 int min = 0;
  28.                 int mid = (min+max)/2;
  29.                 if(key!=arr[mid])
  30.                 {
  31.                         if(key>arr[mid])
  32.                                 min = mid + 1;
  33.                         else if(key<arr[mid])
  34.                                 max = mid - 1;
  35.                         if(min>max)
  36.                                 return -1;
  37.                         mid = (min+max)/2;
  38.                 }
  39.                 return mid;
  40.         }
  41.         public static void Swap(int[] arr,int i,int j)
  42.         {
  43.                 int temp = arr[i];
  44.                 arr[i] = arr[j];
  45.                 arr[j] = temp;
  46.         }
  47.         public static void Show(int[] arr)
  48.         {
  49.                 for(int i=0; i<arr.length; i++)
  50.                 {
  51.                                 System.out.print(arr[i]+",");
  52.                 }
  53.                 System.out.println();
  54.         }
  55. }
复制代码
这个里面Find函数时折半查找，但是我key=8输入进去，按逻辑来说应该是arr[5]来显示，但是最后显示的确实arr[4]，请问这是为什么?谢了
作者: fantacyleo    时间: 2014-7-31 18:07
   if(key!=arr[mid]) 改成   while(key!=arr[mid])
作者: 依然超级赛亚人    时间: 2014-7-31 19:08
本帖最后由 依然超级赛亚人 于 2014-7-31 19:13 编辑

确实如楼上所说，得将if(key!=arr[mid]) 改成   while(key!=arr[mid])。用if判断而不是while的话，程序就没有循环判断，不管你找没找到想查找的数字，最外层if执行一遍就结束了，接着执行下面的语句，也就是直接返回只查找一遍后的mid。
我再仔细说一下吧：当你输入的key为8时，程序会走
if(key>arr[mid])   
min = mid + 1;//此时min=3   
这两句，走完就紧接着走
if(min>max)//只判断，没有进行相应操作（return -1）,只有第三句执行了具体的赋值操作。
return -1;
mid = (min+max)/2;
显然，此时的mid=(3+5)/2，也就是4。然后程序就没有接着判断，直接走出最外层if，直接返回了mid=4，你分析一下是这样吗？




作者: 怀念黑海岸    时间: 2014-7-31 19:32
楼主写的有问题：首先循环方式错了，应该用while表示你要进行多次二分查询，而你用if则表示只查询一次后你就直接把下标返回去了，我们来看下你这程序执行的过程，首先程序运行到find方法，max=5，min=0；mid=2，判断if中的条件 ：if(key!=arr[mid])  
成立，
执行下面的语句： if(key>arr[mid])
成立  mid=mid+1； mid=3；
跳到 if(min>max) 不成立
执行后面的语句：
          mid = (min+max)/2;
mid=（3+5）/2=4；
return mid；
        结果4就被返回了。
  按照你打印的结果就是arr[4], 其实结果并不是这个。
  应该对查找方法内的语句进行修改：
while(arr[mid]!=key){
        if(arr[mid]<key){  
                                    //当中间数小于查找数的时候，此时中间数的下标应该右移一位
        start=mid+1;
        mid=(start+end)/2;
        }
        if(arr[mid]>key){  //当中间数大于查找数时，中间数的下标应该左移一位
                end=mid-1;
                mid=(start+end)/2;
        }
        if(start>end){  //当小数的下标大于大数的下标时，意味着所有数都已经找完了但是却未出现结果
                break;    //跳出程序不再进行执行。
        }
       if(arr[mid]==key){   //当中间数等于查找数时意味找到了
                return mid;
        }
}       
                        
            
作者: rolling-stone    时间: 2014-7-31 23:42
怀念黑海岸 发表于 2014-7-31 19:32
楼主写的有问题：首先循环方式错了，应该用while表示你要进行多次二分查询，而你用if则表示只查询一次后你 ...

谢了，自己写代码写的有点多，没看出来，我想的就是用while，但是不知道怎么搞得写成if了，谢谢.
作者: rolling-stone    时间: 2014-7-31 23:43
依然超级赛亚人 发表于 2014-7-31 19:08
确实如楼上所说，得将if(key!=arr[mid]) 改成   while(key!=arr[mid])。用if判断而不是while的话，程序就没 ...

谢谢了，已经明白了。自己手残给写错了.哈哈.



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