编程论坛 » C语言论坛 » 折半法查找问题

zzt_428 发表于 2008-7-8 22:00

折半法查找问题

我初学编程，写了个程序，先对输入的数从大到小排序，然后用折半法查找其中一个数，但是如果输入的数如果有两个是相同的，这个程序只能返回第一个数的位置，请问各位前辈，怎么样改进才能使它能找到所有相同的数？

#include <stdio.h>
#define N 15
void main()
{
        int i,j,m,n,ch,flag,sign,mid,temp,local,head,end,a[N];
        printf("enter the element of array:\n");
        for(i=0; i<N; i++)
        {
                printf("a[%d]=",i);
                scanf("%d",&a[i]);
                printf("\n");
        }
        for(i=0; i<N; i++)
            printf("%5d",a[i]);

        for(i=0; i<N-1; i++)
    {
                for(j=0; j<N-i-1; j++)
                {
                        if(a[j]<a[j+1])
                        {
                                temp=a[j];
                                a[j]=a[j+1];
                                a[j+1]=temp;
                        }
                }
        }
        printf("the sorted number:\n");
        for(i=1; i<N; i++)
                printf("%5d",a[i]);
        printf("\n");


        flag=1;
        sign=1;
        while(flag)
        {
                local=0;
                head=0;
                end=N-1;
                printf("Enter the number you want to search:\n");
            scanf("%d",&n);
                if(n>a[head] || n<a[end])
                        local=-1;
                while(1==sign && head<=end)
                {
                        mid=(head+end)/2;
                        if(n == a[mid])
                        {
                                local=mid;
                                printf("We've found it!the location is %d",local-1);
                                sign=0;
                        }
                        else
                        {
                                if(n>a[mid])
                                        end=mid-1;
                                else head=mid+1;
                        }


                }
                if(sign || -1==local)
                        printf("Number not found.\n");
                printf("Do you want to continue?(y/n)\n");
                scanf("%c",&ch);

                if('N'==ch || 'n'==ch)
                        flag=0;


    }
}

卧龙孔明 发表于 2008-7-9 08:07

...
这二分代码一般在5行以内吧....

himpo 发表于 2008-7-9 08:26

很简单啊，再对那个数的前后进行比较，如果还相等，就继续前进或后退比较，逐个返回。。

崔园园 发表于 2008-7-9 10:09

for(i=1; i<N; i++)
        printf("%5d",a[i]);
    printf("\n");

这里i应该是从０开始吧

mingshendeshou 发表于 2008-7-9 10:24

加一个标记，如果两个数不相等就改变标记，跳出循环。

查看完整版本: 折半法查找问题