問題：數組查找它和數組排序一樣是重要的計算應用之一，電話公司根據姓氏查找，能容易的找到用戶的電話號碼和繳費情況，在學校成績管理系統可以根據學生的學號，很容易就能查找到學生的成績及相關資料，查找在生活中的應用是十分廣泛，數據排序是一個令人感興趣的問題，這里深入理解兩種最基本的算法：線型查找和二分法查找。
線型查找：把數組的每一個元素和檢索關鍵字比較，安順序從第一個元素一直檢索到要查找的元素，平均來說，程序要把查找關鍵字與一半數組元素進行比較。二分法查找：線型查找法對小型數組和未排序的數組效果較好，但是，對于大型數據來說，線型查找法效率較低。如果已經對數組排序，那么可以使用速度很快的二分法查找.
程序1：線型查找法實現對某個數的查找！
#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：二分法查找法實現對某個數的查找！
#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");
}
效率分析：線型查找擺脫了數組排序的約束，不足之處是不適合大型數據查找，并且查找方法比較老套，如果要找的數在數組中最后一個數n，那么搜索從0開始，一直檢索到n，要經過n次遍歷，時間復雜度：O(n)，而二分查找法中如果查找關鍵字小于數組中間的元素，就查找數組的頭半部分，否則查找數組的后半部分，時間復雜度：O(log2n)，如果在指定子數組中還沒有查找到關鍵字，就再把子數組折半，反復進行這種查找，直到要查找的關鍵字等于子數組中間的元素，或沒有找到關鍵字為止。在最壞的情況下，用二分法查找有1024個元素的數組也只需要比較10次，即用2除1024，連續除10次得到1為止，如果有1048576（2的20次方）個元素，用二分法只要比較20次就可以找到要查找的元素，而用簡單的線型查找則需要進行2的20次方查找，可見二分法比線型查找法的效率要高得多，對10億哥元素的數組來說，平均比較5億次和30次簡直是天壤之別！所以掌握二分法對在龐大的數組庫處理是很有效的！