線性查找和二分查找

         線型查找：把數(shù)組的每一個(gè)元素和檢索關(guān)鍵字比較，安順序從第一個(gè)元素一直檢索到要查找的元素，平均來(lái)說(shuō)，程序要把查找關(guān)鍵字與一半數(shù)組元素進(jìn)行比較。二分法查找：線型查找法對(duì)小型數(shù)組和未排序的數(shù)組效果較好，但是，對(duì)于大型數(shù)據(jù)來(lái)說(shuō)，線型查找法效率較低。如果已經(jīng)對(duì)數(shù)組排序，那么可以使用速度很快的二分法查找.

程序1：線型查找法實(shí)現(xiàn)對(duì)某個(gè)數(shù)的查找！
#include<stdio.h>
#include<stdlib.h>
#define Size 100
int         main()   
{
            int linearSearch(int a[],int key,int size);
            int         a[Size],i,searchKey,element;
            for(i=0;i<Size-1;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<Size-1;j++)
           if(array[j]==key)
              return j;
           return -1;
}

程序2：二分法查找法實(shí)現(xiàn)對(duì)某個(gè)數(shù)的查找！
#include<stdio.h>
#include<stdlib.h>
#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<array[middle])
                  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(i<low||i>high)
                   printf(" ");
                else if(i==middle)
                   printf("%3d*",array[i]);
                else
                   printf("%3d",array[i]);
            printf("\n");
}

           效率分析：線型查找擺脫了數(shù)組排序的約束，不足之處是不適合大型數(shù)據(jù)查找，并且查找方法比較老套，如果要找的數(shù)在數(shù)組中最后一個(gè)數(shù)n，那么搜索從0開始，一直檢索到n，要經(jīng)過(guò)n次遍歷，時(shí)間復(fù)雜度：O(n)，而二分查找法中如果查找關(guān)鍵字小于數(shù)組中間的元素，就查找數(shù)組的頭半部分，否則查找數(shù)組的后半部分，時(shí)間復(fù)雜度：O(log2n)，如果在指定子數(shù)組中還沒有查找到關(guān)鍵字，就再把子數(shù)組折半，反復(fù)進(jìn)行這種查找，直到要查找的關(guān)鍵字等于子數(shù)組中間的元素，或沒有找到關(guān)鍵字為止。在最壞的情況下，用二分法查找有1024個(gè)元素的數(shù)組也只需要比較10次，即用2除1024，連續(xù)除10次得到1為止，如果有1048576（2的20次方）個(gè)元素，用二分法只要比較20次就可以找到要查找的元素，而用簡(jiǎn)單的線型查找則需要進(jìn)行2的20次方查找，可見二分法比線型查找法的效率要高得多，對(duì)10億哥元素的數(shù)組來(lái)說(shuō)，平均比較5億次和30次簡(jiǎn)直是天壤之別！所以掌握二分法對(duì)在龐大的數(shù)組庫(kù)處理是很有效的！

posted on 2011-06-27 13:48 不會(huì)飛的鳥 閱讀(1740) 評(píng)論(0)  編輯 收藏 引用