数据结构实验——折半查找

前子表查找：high=mid-1；
后子表查找：low=mid+1;
算法分析：
1.确定查找有序序列a,置查找区间初值，low为1，high为表长n。
2.当low小于等于high时，循环执行以下操作：
（１）mid取值为high和low的中间值；
（２）将查找值num与中间位置的关键字a[mid]进行比较，若相等则查找成功，输出查找值num在序列a中的位置mid；
（３）若查找值num小于中间位置a[mid],则进入前一子表中查找，high=mid-1;
（4）若查找值num大于中间位置a[mid],则进入后一子表中查找,low=mid+1;
3.循环结束，说明查找空间为空，则查找失败。
程序如下：

#include <stdio.h>
void main()
{
int a[20],num,low,high,mid,i,flag=0;
int n;
printf("请输入有序序列中的元素个数:");
scanf("%d",&n);
printf("请输入%d个有序元素:",n);
for(i=0;i<n;i++)
{
    scanf("%d",&a[i]);
}
printf("请输入要查找的数值:");
scanf("%d",&num);
low=1;
high=n;
while(low<=high)
{
    mid=(low+high)/2;
    printf("low=%d,mid=%d,high=%d\n",low,mid,high);
    if(a[mid]>num)
{
    high=mid-1;//将在前子表中查找
}
if(a[mid]<num)
{
    low=mid+1;//将在后子表中查找
}
if(a[mid]==num)
{
    flag=1;
    break;
}
}
if(flag)
{

    printf("found!\n");
    printf("%d是此序列中的第%d个元素\n",num,mid+1);
    }
    else
    {
        printf("not found!\n");
    }

}

折半查找.png