Question

C语言用二分法查找关键字

一个成绩系统，定义了一个结构体，其中里面有一个字符数组，想用二分法查找来查找关键字，希望有这样的一个函数

Answer 1

#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次简直是天壤之别！所以掌握二分法对在庞大的数组库处理是很有效的！