黑马程序员技术交流社区

标题: 关于折半查找的问题 [打印本页]

作者: 黑马肖凯骏 时间: 2012-3-4 11:20
标题: 关于折半查找的问题
本帖最后由黑马肖凯骏于 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;
      }

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

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

下面是我运行的结果

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

作者: 王杰 时间: 2012-3-4 11:34
本帖最后由苳眠于 2012-3-4 11:35 编辑

折半的for语句有问题！

public static int halfSearch_01(int[] arr,int key)
{
int max,min,mid;
min=0;
max=arr.length-1;
mid=(min+max)>>1;
while (key!=arr[mid])
//for (;key!=arr[mid];)所有能用for的地方都能用while，反之同理；
{
if (min>max)//必须放在第一个判断;
{
return min;
}
else if(key>arr[mid])
{
min=mid+1;
}
else if (key<arr[mid])
{
max=mid-1;
}
mid=(min+max)>>1;//循环以后必须折半;
}
return mid;
}

复制代码

作者: 泮和顺 时间: 2012-3-4 11:59
折半查找只对有顺序的可行吧

作者: 王亚男 时间: 2012-3-4 12:01
本帖最后由 qwert 于 2012-3-4 12:05 编辑

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

public int halfSearch_3(int[] arr,int key)
{
int min=arr.length-1;
int max=0;
int mid = (max+min)/2;
while(key!=arr[mid])
{
if(key>arr[mid])
{
min=mid-1;
}
else if (key<arr[mid])
{
max=mid+1;
}
mid = (max+min)/2;
if(max>min)
{
return -1;
}
}
return mid;
}

复制代码

另外，有点急事，变量名没改过来，您改下就可以了。我这max和min都是反意，只改了逻辑运算符……

作者: 段玉超 时间: 2012-3-4 12:21
折半查找的前提是被查找的数组是有序的，也就是说 halfSearch 函数需要传入一个有序的数组。所以当你传入牌号序的数组时能够得到正确的结果，当你输入没有排序过的数组是就很可能无法得到正确的结果。

作者: 黑马肖凯骏 时间: 2012-3-4 12:29

泮和顺发表于 2012-3-4 11:59
折半查找只对有顺序的可行吧

我是先用函数对无序的进行了排序，再折半查找出现错误的呢！

作者: Destiny 时间: 2012-3-4 13:26
我写了一个你看一下运行没问题~！

class ArrHalf
{
public static void main(String[] args)
{
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);
}
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;
}
public static void bianLi(int a[])//遍历数组并输出
{
for (int x=0;x<a.length ;x++ )
{
System.out.print(a[x]+",");
}
System.out.println();
}
public static void bubbleSort(int a[])//冒泡排序
{
int temp;
for (int x=a.length-1; x>=1 ;x-- )
{
for(int y=0;y<x;y++)
{
if(a[y]>a[y+1]){//如果前一个角标的数比后一个角标的数大，那么交换两个数的位置
temp = a[y];
a[y] = a[y+1];
a[y+1] = temp;
}
}
}
}
}

复制代码

作者: 黑马肖凯骏 时间: 2012-3-4 13:43

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

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

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

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

作者: 黑马肖凯骏 时间: 2012-3-4 14:01

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

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

作者: 黑马肖凯骏 时间: 2012-3-4 14:03

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

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

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

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

作者: 花开~的季节 时间: 2012-3-4 15:09
用Arrays中的方法更快，这个了解一下就ok了，知道原理

作者: 王亚男 时间: 2012-3-4 18:09
本帖最后由 qwert 于 2012-3-4 18:12 编辑

黑马肖凯骏发表于 2012-3-4 14:01
我问题已经解决了！折半查找可以先将数组排序，然后再查找的

排序的方法就在于算法，其实我也是认为这个东西吧，就在于你怎么去思考，锻炼自己的思维罢了。
真正运用起来就像楼上的前辈所说的，用Arrays中的方法更快。
用这个方法，就可以避免因为正序逆序导致的折半失败了。
把正序折半查找和逆序折半查找分别做出来，然后汇总到一个方法里，然后判断数组0脚标和数组.length-1的脚标谁大，因为是有序排列吧，所以这样就可以知道是正序还是逆序了，然后利用三元运算符就可以解决了。

private int halfSearch_2(int[] arr,int key) //这适用于顺序排列
{
int min=0;
int max=arr.length-1;
int mid = (max+min)/2;
while(key!=arr[mid])
{
if(key>arr[mid])
{
min=mid+1;
}
else if (key<arr[mid])
{
max=mid-1;
}
mid = (max+min)/2;
if(min>max)
{
return -1;
}
}
return mid;
}
private int halfSearch_3(int[] arr,int key)//这适用于逆序排列
{
int min=0;
int max=arr.length-1;
int mid = (max+min)/2;
while(key!=arr[mid])
{
if(key>arr[mid])
{
max=mid-1;
}
else if (key<arr[mid])
{
min=mid+1;
}
mid = (max+min)/2;
if(min>max)
{
return -1;
}
}
return mid;
}
public int halfSearch(int[] arr,int key)
{
return arr[0]<arr[arr.length-1]?halfSearch_2(arr,key):halfSearch_3(arr,key); //arr[0]=arr[arr.length-1]我没判断，因为那样的话，是按有序的话，里面就一个数吧。。
}

复制代码

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

t.bubbleSort(arr); //我的bubbleSort是逆序的
t.printArray(arr);
System.out.println("mid="+t.halfSearch(arr,22));
t.selectSort(arr);//选择排序是正序的
t.printArray(arr);
System.out.println("mid="+t.halfSearch(arr,22));

复制代码

作者: 黑马肖凯骏 时间: 2012-3-4 18:52

qwert 发表于 2012-3-4 18:09
排序的方法就在于算法，其实我也是认为这个东西吧，就在于你怎么去思考，锻炼自己的思维罢了。
真正运用 ...

非常感谢，我最终做的方法和你做的是一样的呢！只不过我用IF判断了，你用三元运算符更简洁更高效！！谢谢，问题已经解决啦！

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

黑马程序员IT技术论坛 X3.2