A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 中山狼 于 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("该数字在数组中不存在");
                }        
        }

评分

参与人数 1技术分 +1 收起 理由
杨增坤 + 1

查看全部评分

4 个回复

倒序浏览
你少考虑了一种情况,循环后当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.         }  
复制代码

评分

参与人数 1技术分 +1 收起 理由
杨增坤 + 1

查看全部评分

回复 使用道具 举报
这个问题毕老师视频里面讲解过 我说下我的理解
折半查找主要理解两个问题: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;

评分

参与人数 1技术分 +1 收起 理由
乔兵 + 1

查看全部评分

回复 使用道具 举报
本帖最后由 蓝雨星空 于 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.         }
复制代码
还有就是,功能性代码最好定义到主函数外面,要养成良好的编程习惯……

回复 使用道具 举报
楼主你好,如果问题已解决请将帖子状态修改为提问结束,如果未解决请继续提问,谢谢合作
如果不会修改请看解释帖:http://bbs.itheima.com/thread-89313-1-1.html
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马