折半查找法

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

折半查找的算法思想是将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。代码如下：

#include <stdio.h>

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

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

    key = search(a,16,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;
}