黑马程序员技术交流社区

标题: 关于数组折半查找的一点疑惑 [打印本页]

---

作者: 潘星    时间: 2012-8-9 06:13
标题: 关于数组折半查找的一点疑惑
用折半查找法查数组中的某个数的角标，下面是代码
class ArrDemo
{
        public static void main(String[] args)
        {
                int[] arr={1,2,5,9,12,23,45,89};
                int x=halfSearch(arr,4);
                                System.out.println(x);   
当我查找数组中存在的数据时可以有正确结果，若是我的数据不存在程序为什么会停在那里不动，按理说数组长 度是固定，若查找超过了数组长度循环因该停下来或者出异常啊        }
        public static int halfSearch(int[] arr,int key)
        {
                int min,max,mid;
                min=0;
                max=arr.length-1;
                mid=(min+max)/2;
                while (arr[mid]!=key)
                {
                        if (key<arr[mid])                       
                                max=mid-1;
                        else if(key>arr[mid])                       
                                min=mid+1;                       
                        mid=(min+max)/2;
                }
                return mid;
        }
}

---

作者: 尤洋    时间: 2012-8-9 07:23


while (arr[mid]!=key)
输入数据不存在的话 就相当于while(true)｛｝，当然是无限循环了。
循环只有在条件不满足了 才会停下来，一直为true就一直循环
这跟数组长度无关。
把条件改成while (min<max)即可。

---

作者: 梁志仲    时间: 2012-8-9 08:22
折半查找的条件应该是min<max啊，如果最小脚标都比最大脚标还大了，就说明数组中没有要找的元素。循环条件是判断循环是否能停下来的依据，可以把值代入判断语句，看是否有可能出现循环停不下来的情况。

---

作者: 何明辉    时间: 2012-8-9 08:33
  public static int halfSearch(int[] arr,int key)
        {
                int min,max,mid;
                min=0;
                max=arr.length-1;
                mid=(min+max)/2;
                while (arr[mid]!=key)//楼主此处没有弄清循环条件
                {
                        if (key<arr[mid])                        
                                max=mid-1;
                        else if(key>arr[mid])                        
                                min=mid+1;                        
                        mid=(min+max)/2;
                }
                return mid;
        }
}
上面的while循环是当条件满足时就会一直循环，所以当你输入的值满足时也会进入循环，成了死循环。正确的程序我写在了下面。
class ArrDemo
{
        public static void main(String[] args)
        {
                int[] arr={1,2,5,9,12,23,45,89};
                int x=halfSearch(arr,4);
                                System.out.println(x);   
    }
        public static int halfSearch(int[] arr,int key)
        {
                int min,max,mid;
                min=0;
                max=arr.length-1;
                mid=(min+max)/2;
                if(key<arr[0]||key>arr[arr.length-1])
                 {
                     System.out.println("值不存在！");
                       return -1;
                 }
                while (arr[mid]!=key)
                {
                        if (key<arr[mid])                        
                                max=mid-1;
                        else if(key>arr[mid])                        
                                min=mid+1;                        
                        mid=(min+max)/2;
                }
                return mid;
        }
}

---

作者: hello world    时间: 2012-8-9 08:51
public static int halfSearch(int[] arr,int key)
        {
                int min,max,mid;
                min=0;
                max=arr.length-1;
                mid=(min+max)/2;

                while (arr[mid]!=key)
                {
                       if (key<arr[mid])                        
                                max=mid-1;
                        else if(key>arr[mid])                        
                                min=mid+1;                        
                        else
                                    return mid;
                         mid=(min+max)/2;

                }
                return -1;
                 }
}

---

作者: 王峰    时间: 2012-8-9 09:53
楼主这是一个例子，你看看
/*运行结果：
请按从大到小的顺序输入15个整数：
15 15 13 12 11 10 9 8 7 6 5 4 3 2 1
您输入的数没有排序或有大小相同的数，请重新输入：
15 14 13 12 11 10 9 8 7 6 5 4 3 2 10
您输入的数没有排序或有大小相同的数，请重新输入：
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
请输入要查找的数字：8
8是第8个数字。
*/
#include <stdio.h>
#define N 15

int sorted(int a[N])
{
int i;
for(i=0;i<N-1;i++)
if(a[i]<=a[i+1])
return 0;
return 1;
}

int find(int a[N],int x)
{
int i,min=0,max=N-1;
while(max-min>1)
{
if(a[min]==x)
return min+1;
else if(a[max]==x)
return max+1;
else if(a[(min+max)/2]==x)
return (min+max)/2+1;
if(x>a[(max+min)/2])
max=(max+min)/2;
else
min=(max+min)/2;
}
return 0;
}

main()
{
int a[N],x,i;
printf("请按从大到小的顺序输入%d个整数：\n",N);
for(i=0;i<N;i++)
scanf("%d",&a[i]);
while(!sorted(a))
{
printf("您输入的数没有排序或有大小相同的数，请重新输入：\n");
for(i=0;i<N;i++)
scanf("%d",&a[i]);
}
printf("请输入要查找的数字：");
scanf("%d",&x);
if(!find(a,x))
printf("找不到%d！\n",x);
else
printf("%d是第%d个数字。\n",x,find(a,x));
}

---

作者: zhaosenyang    时间: 2012-8-9 23:33


问题出在这个循环里：   
             while (arr[mid]!=key)
                {
                        if (key<arr[mid])
                                max=mid-1;
                        else if(key>arr[mid])
                                min=mid+1;
                        if (min>max)//因为你没有这个判断，当没有你需要寻找的数据。没有这个判断，那循环条件会一直满足，而你又没有进行这个判断处理，当然会陷入死循环中。这个判断是说当你折半查找最小角标与最大角标交叉了，就说明 这个数值不存在。
                        {
                                return -1;//返回一个-1，说明没有你要查找的这个数值。
                        }
                        mid=(min+max)/2;
                }

---

作者: 潘星    时间: 2012-8-9 23:48
明白了，谢谢各位

---

作者: 潘星    时间: 2012-8-10 00:02
没考虑到会死循环，明白了，谢谢大家

---

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

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