折半的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.         }

复制代码

主函数部分的主体部分我这样子写的
                  
                   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;
         }

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


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

下面是我运行的结果



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

折半查找只对有顺序的可行吧

如果是查倒序的话，代码还得改改：

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. 
   
4.         public static void main(String[] args)
   
5.         {
   
6.                    int [] arr={5,3,2,4,8,34,67,85};
   
7.                  
   
8.                  bianLi(arr);                             //遍历输出原数组
   
9.                  bubbleSort(arr);                   //冒泡排序输出数组
   
10.                  bianLi(arr);                    //遍历数组  验证数组是否已经排序好，验证结果是数组已经排序好！
    
11.                  int a=halfSearch(arr,4);             //折半查找
    
12.                  System.out.print(a);
    
13.                                
    
14.         }
    
15.         public static int halfSearch(int [] arr,int key)//折半查找
    
16.          {
    
17.                  int min = 0;
    
18.                  int max = arr.length-1;
    
19.                  int mid=(min+max)/2;
    
20. 
    
21.                 while(arr[mid]!=key)
    
22.                  {        
    
23.                         
    
24.                         if(key>arr[mid])
    
25.                                  min=mid+1;
    
26.                          else if(key<arr[mid])
    
27.                                  max=mid-1;
    
28.                            if(min>max)
    
29.                                  return -1;
    
30.                         
    
31.                         mid = (min+max)/2;
    
32.                  }
    
33.                  return mid;
    
34.          }
    
35.         public static void bianLi(int a[])//遍历数组并输出
    
36.         {
    
37.                 for (int x=0;x<a.length ;x++ )
    
38.                 {
    
39.                         System.out.print(a[x]+",");
    
40.                 }
    
41.                 System.out.println();
    
42.         }
    
43. 
    
44.         public static void bubbleSort(int a[])//冒泡排序
    
45.         {
    
46.                 int temp;
    
47.                 for (int x=a.length-1; x>=1 ;x-- )
    
48.                 {
    
49.                         for(int y=0;y<x;y++)
    
50.                         {
    
51.                                 if(a[y]>a[y+1]){//如果前一个角标的数比后一个角标的数大 ，那么交换两个数的位置
    
52.                                 temp = a[y];
    
53.                                 a[y] = a[y+1];
    
54.                                 a[y+1] = temp;
    
55.                                 }
    
56.                         }
    
57.                 }
    
58.         }
    
59. }
    

复制代码

Destiny 发表于 2012-3-4 13:26
我写了一个 你看一下 运行没问题~！

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

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

所以前后矛盾，始终是出不来结果！

段玉超 发表于 2012-3-4 12:21
折半查找 的前提是 被查找的数组是有序的，也就是说  halfSearch 函数需要传入一个 有序的数组。所以 当你 ...

我问题已经解决了！折半查找可以先将数组排序，然后再查找的

qwert 发表于 2012-3-4 12:01
如果是查倒序的话，代码还得改改：另外，有点急事，变量名没改过来，您改下就可以了。我这max和min都是反意 ...

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

问题就出在这里啦，弄得我还去分析内存中的存储问题去了！！！郁闷呀！！ 谢谢帮忙解决了问题！

查找本就是数据结构里面的一种算法，前提就是数组得有序的，定义就是这样定的，具体跟算法有关，因为,前后有比较，跟你相比较的那个数有比较，乱序的话，一会前大后小，一会后小前大，电脑也读不出程序结果.
这种算法得深入体会并理解。
数据的组织方式就是数据结构，跟逻辑结构，物理结构都有关....

用Arrays中的方法更快，这个了解一下就ok了，知道原理

黑马肖凯骏 发表于 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. 
    
27.         private int halfSearch_3(int[] arr,int key)//这适用于逆序排列
    
28.         {
    
29.                
    
30.                         int min=0;
    
31.                         int max=arr.length-1;
    
32.                         int mid = (max+min)/2;
    
33.                         while(key!=arr[mid])
    
34.                         {
    
35.                                 if(key>arr[mid])
    
36.                                 {
    
37.                                         max=mid-1;
    
38.                                 }
    
39.                                 else if (key<arr[mid])
    
40.                                 {
    
41.                                         min=mid+1;
    
42.                                 }
    
43.                                 mid = (max+min)/2;
    
44.                        
    
45.                                 if(min>max)
    
46.                                 {
    
47.                                         return -1;
    
48.                                 }
    
49.                        
    
50.                                
    
51.                         }
    
52.                                 return mid;
    
53.         }
    
54. 
    
55. public int halfSearch(int[] arr,int key)
    
56.         {
    
57.        
    
58.                 return arr[0]<arr[arr.length-1]?halfSearch_2(arr,key):halfSearch_3(arr,key); //arr[0]=arr[arr.length-1]我没判断，因为那样的话，是按有序的话，里面就一个数吧。。
    
59.                        
    
60.         }
    

复制代码

然后主函数里是这样的，我用了俩类。

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判断了，你用三元运算符更简洁更高效！！谢谢，问题已经解决啦！