线型查找和二分法查找

   问题：数组查找和数组排序一样,是重要的计算应用之一。电话公司根据姓氏查找，能容易的找到用户的电话号码和缴费情况；学校成绩管理系统可以根据学生的学号，很容易就能查找到学生的成绩及相关资料。查找在生活中的应用十分广泛，数据排序是一个令人感兴趣的问题，这里深入理解两种最基本的算法：线型查找和二分法查找。

   线型查找：把数组的每一个元素和检索关键字比较，按顺序从第一个元素一直检索到要查找的元素，平均来说，程序要把查找关键字与一半的数组元素进行比较。

   二分法查找：线型查找法对小型数组和未排序的数组效果较好，但是，对于大型数据来说，线型查找法效率较低。如果已经对数组排序，那么可以使用速度很快的二分法查找.

程序1：线型查找法实现对某个数的查找！
#include
#include
#define Size 100
int main()
{   int linearSearch(int a[], int key, int size);

    int a[Size], i, searchKey, element;

    for(i=0; i        a[i]=2*i;

    printf("Enter integer search key:\n");
    scanf("%d",&searchKey);
    element=linearSearch(a,searchKey,Size);
    if(element!=-1)
        printf("Found value in element %d !\n",element);
    else
        printf("Value is not found!\n");

    system("pause");
}   

int linearSearch(int array[],int key,int size)
{
    int j;
    for(j=0; j        if(array[j]==key)
            return j;
    return -1;
}

程序2：二分法查找法实现对某个数的查找！
#include
#include
#define Size 15

int main()
{
    int binarySearch(int [], int, int, int);
    void printHeader(void);
    void printRow(int [],int,int,int);

    int a[Size],i,key,element;
    for(i=0;i <= Size-1;i++)
        a[i]=2*i;

    printf("Enter a number between 0 and 28:");
    scanf("%d",&key);
    printHeader();

    element=binarySearch(a, key, 0, Size-1);
    if(element!=-1)
        printf("\n%d found in array element %d !\n",key,element);
    else
        printf("\n%d is not found!\n",key);
         
    system("pause");
}  

void printHeader()
{
    int i;
    printf("\nSubscripts:\n");
    for(i=0;i<=Size-1;i++)
        printf("%3d",i);
    printf("\n");
    for(i=1;i<=4*Size;i++)
        printf("-");
    printf("\n");
}

int binarySearch(int array[], int searchKey, int low, int high)
{
    void printRow(int array[],int low,int middle,int high);
    int middle;

    while(low<=high){
        middle=(low+high)/2;
        printRow(array,low,middle,high);
        if(searchKey==array[middle])
            return middle;
        else if(searchKey            high=middle-1;
        else
            low=middle+1;
     }

     return -1;
}

void printRow(int array[],int low,int middle,int high)
{
    int i;
    for(i=0;i<=Size-1;i++)
        if(ihigh)
            printf(" ");
        else if(i==middle)
            printf("%3d*",array[i]);
        else
            printf("%3d",array[i]);
    printf("\n");
}

   效率分析：线型查找摆脱了数组排序的约束，不足之处是不适合大型数据查找，并且查找方法比较老套，如果要找的数是数组中最后一个数n，那么搜索从0开始，一直检索到n，要经过n次遍历，时间复杂度：O(n)，而二分查找法中如果查找关键字小于数组中间的元素，就查找数组的头半部分，否则查找数组的后半部分，时间复杂度：O(log2N)，如果在指定子数组中还没有查找到关键字，就再把子数组折半，反复进行这种查找，直到要查找的关键字等于子数组中间的元素，或没有找到关键字为止。在最坏的情况下，用二分法查找有1024个元素的数组也只需要比较10次，即用2除1024，连续除10次得到1为止，如果有1048576（2的20次方）个元素，用二分法只要比较20次就可以找到要查找的元素，而用简单的线型查找则需要进行2的20次方查找，可见二分法比线型查找法的效率要高得多，对10亿个元素的数组来说，平均比较5亿次和30次简直是天壤之别！所以掌握二分法对在庞大的数组库处理是很有效的！