黑马程序员技术交流社区

标题: 做折半查找的遇到问题,帮忙啊各位，谢谢啦 [打印本页]
作者: 中山狼    时间: 2013-10-24 22:58
标题: 做折半查找的遇到问题,帮忙啊各位，谢谢啦
本帖最后由 中山狼 于 2013-10-24 22:59 编辑

//折半查找，主要是查找数据在有序数组中的位置
        public static void halfSearch(int[] arr,int num){
                //定义一个有序的数组
                //int []arr={12,23,34,45,56,67,78,89,90};
                //定义需要查找的数据
                //int num=34;
                //定义用于标示的下限索引
                int min=0;
                //定义用于表示的上线索引
                int max=arr.length-1;
                //因为不知道具体位置，所以通过while循环进行数组遍历
                while(min<max){
                        //将下限与上限的索引号相加除以2，得到一个标引号，比较num与该表引号的值得大小
                int id=(min+max)/2;
                if(num==arr[id]){//如果遇到id与查找数字相同的情况下跳出循环   
                        //在此处，我将num和arr[id]的位置放反了，程序可以运行，但是没有结果
                                System.out.println(num+"在数组中第"+(id+1)+"的位置");
                                break;
                        }else{
                                if(num>arr[id]){
                                        min=id+1;//遇到num比折半查找中间索引大的情况，就将下线索引的值改为id+1
                                }else{
                                        max=id-1;//遇到num比折半查找中间索引小的情况，就将上限索引的值改为id-1
                                }
                        }
                }
                if(min>max){
                        System.out.println("该数字在数组中不存在");
                }        
        }
作者: 周学彬    时间: 2013-10-24 23:07
你少考虑了一种情况，循环后当min=max时，可以直接打印结果了
在while代码块后面添加一句就行了。
代码如下：
  1.     public static void halfSearch(int[] arr,int num){
  2.         //定义一个有序的数组
  3.         //int []arr={12,23,34,45,56,67,78,89,90};
  4.         //定义需要查找的数据
  5.         //int num=34;
  6.         //定义用于标示的下限索引
  7.         int min=0;
  8.         //定义用于表示的上线索引
  9.         int max=arr.length-1;
  10.         //因为不知道具体位置，所以通过while循环进行数组遍历
  11.         while(min<max){
  12.                 //将下限与上限的索引号相加除以2，得到一个标引号，比较num与该表引号的值得大小
  13.         int id=(min+max)/2;
  14.         if(num==arr[id]){//如果遇到id与查找数字相同的情况下跳出循环   
  15.                 //在此处，我将num和arr[id]的位置放反了，程序可以运行，但是没有结果
  16.                         System.out.println(num+"在数组中第"+(id+1)+"的位置");
  17.                         break;
  18.                 }else{
  19.                         if(num>arr[id]){
  20.                                 min=id+1;//遇到num比折半查找中间索引大的情况，就将下线索引的值改为id+1
  21.                         }else{
  22.                                 max=id-1;//遇到num比折半查找中间索引小的情况，就将上限索引的值改为id-1
  23.                         }
  24.                 }
  25.         }
  26.         if (min == max)
  27.                 System.out.println(num+"在数组中第"+(min+1)+"的位置");
  28.         if(min>max){
  29.                 System.out.println("该数字在数组中不存在");
  30.         }  
复制代码
作者: ixiangfeng    时间: 2013-10-24 23:58
这个问题毕老师视频里面讲解过 我说下我的理解
折半查找主要理解两个问题：1.折半的条件（何时该继续折半）;2.折半角标的变化（需要折半后max、min、和mid的关系）
折半条件有两个：1. while(arr[mid] !=key){ if(min > max ) return -1;}      
                         2.while(min <= max){}

折半角标变化：1.当arr[mid]>key时，即key在数组前半段，故应将max移到前面，即max=mid-1;
                     2.当arr[mid]<key时，即key在数组后半段，故应将min移到后面，即min=mid+1;
作者: 蓝雨星空    时间: 2013-10-25 06:56
本帖最后由 蓝雨星空 于 2013-10-25 07:01 编辑

while循环的条件修改一下就OK了：
  1. //折半查找，主要是查找数据在有序数组中的位置
  2.         public static void halfSearch(int[] arr,int num){
  3.                 //定义一个有序的数组
  4.                 //int []arr={12,23,34,45,56,67,78,89,90};
  5.                 //定义需要查找的数据
  6.                 //int num=34;
  7.                 //定义用于标示的下限索引
  8.                 int min=0;
  9.                 //定义用于表示的上线索引
  10.                 int max=arr.length-1;
  11.                 //因为不知道具体位置，所以通过while循环进行数组遍历
  12.                 while(min<=max){    // 这里的条件修改一下，加个等号
  13.                         //将下限与上限的索引号相加除以2，得到一个标引号，比较num与该表引号的值得大小
  14.                 int id=(min+max)/2;
  15.                 if(num==arr[id]){//如果遇到id与查找数字相同的情况下跳出循环   
  16.                         //在此处，我将num和arr[id]的位置放反了，程序可以运行，但是没有结果
  17.                                 System.out.println(num+"在数组中第"+(id+1)+"的位置");
  18.                                 break;
  19.                         }else{
  20.                                 if(num>arr[id]){
  21.                                         min=id+1;//遇到num比折半查找中间索引大的情况，就将下线索引的值改为id+1
  22.                                 }else{
  23.                                         max=id-1;//遇到num比折半查找中间索引小的情况，就将上限索引的值改为id-1
  24.                                 }
  25.                         }
  26.                 }
  27.                 if(min>max){
  28.                         System.out.println("该数字在数组中不存在");
  29.                 }        
  30.         }
复制代码
还有就是，功能性代码最好定义到主函数外面，要养成良好的编程习惯……

作者: 乔兵    时间: 2013-10-25 08:02
楼主你好，如果问题已解决请将帖子状态修改为提问结束，如果未解决请继续提问，谢谢合作
如果不会修改请看解释帖：http://bbs.itheima.com/thread-89313-1-1.html



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