C程序习题-用折半查找法进行查找[7.9]

时间：2010-08-04 来源：chengxiaopeng

有15个数由小到大顺序存放在一个数组中，输入一个数，要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中，则打印出“无此数”。这道题，主要是折半查找法，折半查找法的原理是，首先找到中间的那个值，如果中间值就是要查找的值，就跳出查找。如果中间的那个值比查找的值大，则将中间索引值赋值给查找的终点值。如果中间的值比查找的值小，则将中间索引值复制给查找的开始索引值。直到开始值大于等于中间索引值，查找结束。根据此原理编写代码如下：

#include <stdio.h>

int search(int[],int,int);
int main(int argc, int *argv[])
{
    int a[15] = {3,5,7,8,10,20,30,40,55,67,87,90,100,111,134};
    int i,search_value;
    int key;
    for (i = 0; i < 15; i++)
    {
        printf("%4d",a[i]);
    }

    printf("\nplease input search number:");
    scanf("%d",&search_value);

    key = search(a,15,search_value);

    if (key != -1)
    {
       printf("search %d in %d number.\n",search_value,key);
    }
    else
    {
        printf("not search %d.\n",search_value);
    }
    system("pause");
    return 0;
}

int search(int arr[], int n, int key)
{
           int begin = 0,end = n, mid = end / 2;
           int result = -1;
           while(begin < mid && arr[mid] != key)
           {


             if (key > arr[mid])
             {
                begin = mid;
             }
             else if (key < arr[mid])
             {
                end = mid;
             }
             else
             {
                 ;
             }
             mid = (begin + end) / 2;
           }

           if (arr[mid] == key)
           {
                result = mid;
           }
           return result;
}