UC知道这个这折半算法错在哪里？
来源：百度知道 编辑：UC知道 时间：2024/05/14 09:55:26
输入在数组里的数没有问题，但当输入不在数组里的数出现死循环。
#include<stdio.h>
#include<conio.h>
void main()
{int i,j,k,d,a[10];
int pos(int low,int high,int arra[10],int tar);
clrscr();
printf("\nplease intput 10 numbers\n");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<9;i++)
for(j=i+1;j<10;j++)
if(a[i]>a[j])
{
for(i=0;i<10;i++)
{
for(j=i+1;j<10;j++)
if(a[i]>a[j])
{
k=a[i];
a[i]=a[j];
a[j]=k;
}
printf("%-5d",a[i]);
}
i=10;
j=10;
}
printf("\nPlease input the number that you want search.\n");
scanf("%d",&k);
d=pos(0,9,a,k);
if(d==-1)
printf("\nSorry,the number is not exist in the array.\n");
else
printf("\nThe position of the number is %d.\n",d);
}
in
#include<stdio.h>
#include<conio.h>
void main()
{int i,j,k,d,a[10];
int pos(int low,int high,int arra[10],int tar);
clrscr();
printf("\nplease intput 10 numbers\n");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<9;i++)
for(j=i+1;j<10;j++)
if(a[i]>a[j])
{
for(i=0;i<10;i++)
{
for(j=i+1;j<10;j++)
if(a[i]>a[j])
{
k=a[i];
a[i]=a[j];
a[j]=k;
}
printf("%-5d",a[i]);
}
i=10;
j=10;
}
printf("\nPlease input the number that you want search.\n");
scanf("%d",&k);
d=pos(0,9,a,k);
if(d==-1)
printf("\nSorry,the number is not exist in the array.\n");
else
printf("\nThe position of the number is %d.\n",d);
}
in
原程序这一行有问题：
while(tar!=arra[mid]&&low<high)
可以改成：
while(tar!=arra[mid]&&high-low>1)
(已测试通过)
下面说明原因。
当查找的数不在列表中，循环到low和high相差1时，
永远是mid=(low+high)/2=low，low和high的值都不再改变，
而且满足你设的条件
(tar!=arra[mid]&&low<high)
所以出现了无限循环。
而事实上low和high相差1时，无需再取中间（中间没有数了）。
可以参考上面的改法。