黑马程序员技术交流社区

标题: 关于数组排序后在折半查找的问题 [打印本页]

---

作者: 苏伯亚    时间: 2014-4-9 20:07
标题: 关于数组排序后在折半查找的问题
开始复习后看到了排序和查找。我随机输入一个不是顺序的数组。先排序后在折半查找，为什么总是返回值不对？下面是代码：
class Demo
{
        public static void main(String[] args)
        {
                int [] arr={1,31,65,74,98,100};
                bianli(arr);
                paixu(arr);
                //maopo(arr);
                bianli(arr);
                int p=getIndex(arr,31)+1;
                System.out.println(p);
               
        }

        public static void bianli(int [] arr)//遍历数组并输出
        {
                System.out.print("【");
                for (int x=0;x<arr.length ;x++ )
                {
                        if(x!=arr.length-1)
                        System.out.print(arr[x]+",");
                        else
                                System.out.println(arr[x]+"】");
                }
        }

           public static void paixu(int [] arr)//选择排序
        {
                for (int x=0;x<arr.length-1 ;x++ )
                {
                        for (int y=x+1;y<arr.length ;y++ )
                        {
                            if (arr[x]<arr[y])
                             {
                                    swp(arr,x,y);
                             }
                        }
                }
        }
        public static void maopo(int [] arr)//冒泡排序
        {
                for (int x=0;x<arr.length-1 ;x++ )
                {
                        for (int y=0;y<arr.length-x-1 ;y++ )
                        {
                                if (arr[y]<arr[y+1])
                             {
                                   swp(arr,y,y+1);
                             }
                        }
                }

        }
        public static void swp(int [] arr,int a,int b)//交换两个变量的值
        {
                arr[a]=arr[a]^arr[b];
                arr[b]=arr[a]^arr[b];
                arr[a]=arr[b]^arr[a];
        }
        public static int getIndex(int [] arr,int key)//折半查找 返回角标。
        {
                int min=0,max=arr.length-1,mid;
                //System.out.println("min="+min);
                //System.out.println("max="+max);
                while(min<=max)
                {
                        mid=(max+min)>>1;
                        //System.out.println("mid="+mid);
                        if(key>arr[mid])
                                min=mid+1;
                        else if(key<arr[mid])
                                max=mid-1;
                        else
                                return mid;
                }
                return -1;
        }
}


如果不进行排序直接查找返回值就是正确的。但是一旦进行了排序操作返回值就是0。这是为什么呢？
即使输入的是有序的数组，进行排序后返回值也是错的。求解答

---

作者: tiuwing    时间: 2014-4-9 21:39
按你的折半查找的算法，参数必须是从小到大的排序，你的排序方法却是从大到小的。。。把排序中的
if (arr[x]<arr[y])  改成  if (arr[x]>arr[y])就行了。

---

作者: muma    时间: 2014-4-9 22:09
折半查询必须保证数组中是数有顺序才可以

---

作者: jingdou56    时间: 2014-4-9 22:30
这是你排序前和排序后的结果：

【1,31,65,74,98,100】

【100,98,74,65,31,1】

你排序之后是倒序的，

所以在折半时也应该按照倒序的思路来，

要么就把排序调整一下!

---

作者: 张耀扬    时间: 2014-4-9 22:42
  while(min<=max)
                {
                        mid=(max+min)>>1;
                        //System.out.println("mid="+mid);
                        if(key>arr[mid])
                                min=mid+1;//楼主的排序是降序排列, 如果要找的比arr[mid]大, 则应该是凌max=mid吧
                        else if(key<arr[mid])
                                max=mid-1;// 同样, 要是key比arr[mid]小, 则需要改变的是min=mid
                        else
                                return mid;
                }
或者 楼主把上面两个判断中,>改成< , <改成> 可以得到想要的结果.
用eclipse跑一下, 可以结果如下:
【1,31,65,74,98,100】
【100,98,74,65,31,1】
5

---

作者: 苏伯亚    时间: 2014-4-10 09:04

张耀扬 发表于 2014-4-9 22:42
while(min>1;
                        //System.out.println("mid="+mid);
                        if( ...

嗯 谢谢 忽视这个小地方了

---

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

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