欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

折半查找法问题

程序员文章站 2024-03-20 18:28:34
...

1.问题描述
有15个数存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中第几个元素值。如果该数不在数组中,则打印出“无此数”。
2.编程分析
首先要把15个数排序,这里选择的是选择排序法,然后用折半查找法寻找此数num,这里需要定义三个变量分别是数组首部top,数组中部mid和数组尾部bot。即top=0,bot=14,mid=(top+bot)/2。然后利用循环结构while来寻找此数,循环条件是(top<=bot),如果a[mid]=num,则查找成功,输出该数在数组里的下标,如果a[mid]<num,则top=mid+1,如果a[mid]>num,则bot=mid-1。如果循环结束即top>bot,则输出“无此数”。

用C语言实现代码如下:

#include <stdio.h>
#include <stdlib.h>
int main()
{
	int i,j,k,p,q,num,top=0,mid,bot=14;
    int a[15];
    for(i=0;i<15;i++)
		scanf("%d",&a[i]);
    for(i=0;i<15;i++)
    {
		p=i;
        q=a[i];
        for(j=i+1;j<15;j++)
        {
			if(q>a[j])
            {
				p=j;
                q=a[j];
            }
        }
        if(p!=i)
        {
			k=a[i];
            a[i]=a[p];
            a[p]=k;
        }
        printf("%d\t",a[i]);
    }
    printf("\n请输入要查找的数:");
    scanf("%d",&num);   
    mid=(top+bot)/2;
    while(top<=bot)
    {
		if(a[mid]==num)
			break;
        else
			if(a[mid]>num)
				bot=mid-1;
            else
				top=mid+1;
        mid=(top+bot)/2;
    }
    if(top>bot)
		printf("无此数\n");
    else
		printf("查找的数在数组的第%d个位置\n",mid+1);
	system("pause");
	return 0;
}