黑马程序员技术交流社区

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

作者: 潘星    时间: 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
本帖最后由 尤洋 于 2012-8-9 08:48 编辑

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
本帖最后由 赵森羊 于 2012-8-9 23:37 编辑

问题出在这个循环里:   
             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