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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 黑马肖凯骏 中级黑马   /  2012-3-4 11:20  /  2690 人查看  /  13 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 苳眠 于 2012-3-4 11:35 编辑

折半的for语句有问题!
  1. public static int halfSearch_01(int[] arr,int key)
  2.         {
  3.                 int max,min,mid;
  4.                 min=0;
  5.                 max=arr.length-1;
  6.                 mid=(min+max)>>1;
  7.                 while (key!=arr[mid])
  8.                 //for (;key!=arr[mid];)所有能用for的地方都能用while,反之同理;
  9.                 {
  10.                         if (min>max)//必须放在第一个判断;
  11.                         {
  12.                                 return min;
  13.                         }
  14.                         else if(key>arr[mid])
  15.                         {
  16.                                 min=mid+1;
  17.                         }
  18.                         else if (key<arr[mid])
  19.                         {
  20.                                 max=mid-1;
  21.                         }
  22.                         mid=(min+max)>>1;//循环以后必须折半;
  23.                 }
  24.                 return mid;
  25.         }
复制代码
回复 使用道具 举报
本帖最后由 黑马肖凯骏 于 2012-3-4 12:41 编辑

主函数部分的主体部分我这样子写的
                  
                   int [] arr={5,3,2,4,8,34,67,85};
                 
                           bianli(arr);                             //遍历输出原数组
                 bubbleSort(arr);                   //冒泡排序输出数组
                 bianli(arr);                    //遍历数组  验证数组是否已经排序好,验证结果是数组已经排序好!
                 int a=halfSearch(arr,4);             //折半查找
                 System.out.print(a);
数组有arr引用,所以对数组进行排序后,数组依然是存在的,不会成为垃圾,通过之后的bianli函数,验证了数组已经排序OK了,但是采用折半查找为什么没有结果呢!而输入一个已经排序好的数组是没有问题的呢!

折半查找的函数部分
public static int halfSearch(int [] arr,int key)
         {
                 int min = 0;
                 int max = arr.length-1;
                 int mid=(min+max)/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 = (min+max)/2;
                 }
                 return mid;
         }

如上所述,如果是使用已经排序好的数组进行折半查找是没有问题。


但是我将不规则数组排序后,再折半查找就出不来结果了!这是为什么呢!请高手帮我解答一下呢!

下面是我运行的结果



光标停止不动,无法得到预想结果,如果采用排序好的数组的话,程序正常运行!

13 个回复

倒序浏览
折半查找只对有顺序的可行吧
回复 使用道具 举报
本帖最后由 qwert 于 2012-3-4 12:05 编辑

如果是查倒序的话,代码还得改改:
  1. public int halfSearch_3(int[] arr,int key)
  2.         {
  3.                 int min=arr.length-1;
  4.                 int max=0;
  5.                 int mid = (max+min)/2;
  6.                 while(key!=arr[mid])
  7.                 {
  8.                         if(key>arr[mid])
  9.                         {
  10.                                 min=mid-1;
  11.                         }
  12.                         else if (key<arr[mid])
  13.                         {
  14.                                 max=mid+1;
  15.                         }
  16.                         mid = (max+min)/2;
  17.                        
  18.                         if(max>min)
  19.                         {
  20.                                 return -1;
  21.                         }
  22.                        
  23.                 }
  24.                         return mid;
  25.         }
复制代码
另外,有点急事,变量名没改过来,您改下就可以了。我这max和min都是反意,只改了逻辑运算符……
回复 使用道具 举报
折半查找 的前提是 被查找的数组是有序的,也就是说  halfSearch 函数需要传入一个 有序的数组。所以 当你传入 牌号序的数组时能够得到正确的结果,当你输入没有排序过的数组是就很可能无法得到正确的结果。

回复 使用道具 举报
泮和顺 发表于 2012-3-4 11:59
折半查找只对有顺序的可行吧

我是先用函数对无序的进行了排序,再折半查找出现错误的呢!
回复 使用道具 举报
我写了一个 你看一下 运行没问题~!
  1. class ArrHalf
  2. {

  3.         public static void main(String[] args)
  4.         {
  5.                    int [] arr={5,3,2,4,8,34,67,85};
  6.                  
  7.                  bianLi(arr);                             //遍历输出原数组
  8.                  bubbleSort(arr);                   //冒泡排序输出数组
  9.                  bianLi(arr);                    //遍历数组  验证数组是否已经排序好,验证结果是数组已经排序好!
  10.                  int a=halfSearch(arr,4);             //折半查找
  11.                  System.out.print(a);
  12.                                
  13.         }
  14.         public static int halfSearch(int [] arr,int key)//折半查找
  15.          {
  16.                  int min = 0;
  17.                  int max = arr.length-1;
  18.                  int mid=(min+max)/2;

  19.                 while(arr[mid]!=key)
  20.                  {        
  21.                         
  22.                         if(key>arr[mid])
  23.                                  min=mid+1;
  24.                          else if(key<arr[mid])
  25.                                  max=mid-1;
  26.                            if(min>max)
  27.                                  return -1;
  28.                         
  29.                         mid = (min+max)/2;
  30.                  }
  31.                  return mid;
  32.          }
  33.         public static void bianLi(int a[])//遍历数组并输出
  34.         {
  35.                 for (int x=0;x<a.length ;x++ )
  36.                 {
  37.                         System.out.print(a[x]+",");
  38.                 }
  39.                 System.out.println();
  40.         }

  41.         public static void bubbleSort(int a[])//冒泡排序
  42.         {
  43.                 int temp;
  44.                 for (int x=a.length-1; x>=1 ;x-- )
  45.                 {
  46.                         for(int y=0;y<x;y++)
  47.                         {
  48.                                 if(a[y]>a[y+1]){//如果前一个角标的数比后一个角标的数大 ,那么交换两个数的位置
  49.                                 temp = a[y];
  50.                                 a[y] = a[y+1];
  51.                                 a[y+1] = temp;
  52.                                 }
  53.                         }
  54.                 }
  55.         }
  56. }
复制代码
回复 使用道具 举报
Destiny 发表于 2012-3-4 13:26
我写了一个 你看一下 运行没问题~!

谢谢,你运行的结果是正确的,
我知道  我什么地方错了

我冒泡排序是按从大到小排序的,而前面我定义的Mid 判断的条件是按照从小到大的顺序查找的

所以前后矛盾,始终是出不来结果!
回复 使用道具 举报
段玉超 发表于 2012-3-4 12:21
折半查找 的前提是 被查找的数组是有序的,也就是说  halfSearch 函数需要传入一个 有序的数组。所以 当你 ...

我问题已经解决了!折半查找可以先将数组排序,然后再查找的
回复 使用道具 举报
qwert 发表于 2012-3-4 12:01
如果是查倒序的话,代码还得改改:另外,有点急事,变量名没改过来,您改下就可以了。我这max和min都是反意 ...

嗯 谢谢,我看了下,我的问题主要是我的冒泡排序是倒序排列,而我折半查找条件没有改过来了呢!!

问题就出在这里啦,弄得我还去分析内存中的存储问题去了!!!郁闷呀!! 谢谢帮忙解决了问题!
回复 使用道具 举报
查找本就是数据结构里面的一种算法,前提就是数组得有序的,定义就是这样定的,具体跟算法有关,因为,前后有比较,跟你相比较的那个数有比较,乱序的话,一会前大后小,一会后小前大,电脑也读不出程序结果.
这种算法得深入体会并理解。
数据的组织方式就是数据结构,跟逻辑结构,物理结构都有关....
回复 使用道具 举报
用Arrays中的方法更快,这个了解一下就ok了,知道原理
回复 使用道具 举报
本帖最后由 qwert 于 2012-3-4 18:12 编辑
黑马肖凯骏 发表于 2012-3-4 14:01
我问题已经解决了!折半查找可以先将数组排序,然后再查找的


排序的方法就在于算法,其实我也是认为这个东西吧,就在于你怎么去思考,锻炼自己的思维罢了。
真正运用起来就像楼上的前辈所说的,用Arrays中的方法更快。
用这个方法,就可以避免因为正序逆序导致的折半失败了。
把正序折半查找和逆序折半查找分别做出来,然后汇总到一个方法里,然后判断数组0脚标和数组.length-1的脚标谁大,因为是有序排列吧,所以这样就可以知道是正序还是逆序了,然后利用三元运算符就可以解决了。
  1. private int halfSearch_2(int[] arr,int key) //这适用于顺序排列
  2.         {
  3.                 int min=0;
  4.                 int max=arr.length-1;
  5.                 int mid = (max+min)/2;
  6.                 while(key!=arr[mid])
  7.                 {
  8.                         if(key>arr[mid])
  9.                         {
  10.                                 min=mid+1;
  11.                         }
  12.                         else if (key<arr[mid])
  13.                         {
  14.                                 max=mid-1;
  15.                         }
  16.                         mid = (max+min)/2;
  17.                        
  18.                         if(min>max)
  19.                         {
  20.                                 return -1;
  21.                         }
  22.                        
  23.                 }
  24.                         return mid;
  25.         }

  26.         private int halfSearch_3(int[] arr,int key)//这适用于逆序排列
  27.         {
  28.                
  29.                         int min=0;
  30.                         int max=arr.length-1;
  31.                         int mid = (max+min)/2;
  32.                         while(key!=arr[mid])
  33.                         {
  34.                                 if(key>arr[mid])
  35.                                 {
  36.                                         max=mid-1;
  37.                                 }
  38.                                 else if (key<arr[mid])
  39.                                 {
  40.                                         min=mid+1;
  41.                                 }
  42.                                 mid = (max+min)/2;
  43.                        
  44.                                 if(min>max)
  45.                                 {
  46.                                         return -1;
  47.                                 }
  48.                        
  49.                                
  50.                         }
  51.                                 return mid;
  52.         }

  53. public int halfSearch(int[] arr,int key)
  54.         {
  55.        
  56.                 return arr[0]<arr[arr.length-1]?halfSearch_2(arr,key):halfSearch_3(arr,key); //arr[0]=arr[arr.length-1]我没判断,因为那样的话,是按有序的话,里面就一个数吧。。
  57.                        
  58.         }
复制代码
然后主函数里是这样的,我用了俩类。
  1. t.bubbleSort(arr); //我的bubbleSort是逆序的
  2.                 t.printArray(arr);
  3.                 System.out.println("mid="+t.halfSearch(arr,22));
  4.                 t.selectSort(arr);//选择排序是正序的
  5.                 t.printArray(arr);
  6.                 System.out.println("mid="+t.halfSearch(arr,22));
复制代码
回复 使用道具 举报
qwert 发表于 2012-3-4 18:09
排序的方法就在于算法,其实我也是认为这个东西吧,就在于你怎么去思考,锻炼自己的思维罢了。
真正运用 ...

非常感谢,我最终做的方法和你做的是一样的呢!只不过我用IF判断了,你用三元运算符更简洁更高效!!谢谢,问题已经解决啦!
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马