数据结构---二分查找算法-白红宇

1. 请自行学习二分查找算法，并实现以下函数：

- 1.1

在一个已排序的整型数组array

中，假设已知array

数组的元素个数为n

，需要查找的关键值为key

，要求在array

数组中查找值为key

的数字，并返回该数字在数组中对应的索引值。请设计并实现该函数。

#include<stdio.h>

int bsearch1(int *array,int key,int n)

{

int low=0,high=n-1,mid;

while(low<=high)

{

mid=(low+high)/2;

if(array[mid]==key)

{

printf("find out the key and its index is %d\n",mid);

return mid;

}

if(array[0]<array[n-1])

{

if( array[mid] > key )

high = mid-1;

else

low = mid+1;

}

else

{

if(key<array[mid])

low=mid+1;

else

high=mid-1;

}

printf("key is not in this array!\n");

return -1;

}

- 1.2

在标准C

库中，二分查找函数bsearch

的原型如下：

void *bsearch(const void *key, const void *base, size_t nmemb,

size_t size, int (*compar)(const void *, const void *))

实现代码如下：

void* bsearch2(const void *key, const void *base, size_t nmemb,size_t size, int (*compar)(const void *, const void *))

{

size_t low=0,high=nmemb-1;

size_t mid;

void *p;

int result;

while(low <=high)

{

mid=(low+high) /2;

p=(void*) ( (char*)base +mid *size);

注意

char

的使用

，p point to mid；

result=(*compar)(key,p);

if(result==0)

return p;

else if(result < 0)

high=mid-1;

else

low=mid+1;

}

return NULL;

}

int compare(const void *a,const void *b )//compare的实现；

{

return (*(int*)a-*(int*)b);

}

int main()

{

int a[8]={1,3,4,7,9,10,14,16};

int b[8]={16,14,10,9,7,4,3,1};

int *q;

bsearch1(a,3,8);

bsearch1(b,3,8);

q=(int*)bsearch2(&a[3],a,8,4,compare);

printf("the key's index is %d\n",q-a);

return 0;

}

本文转自曾永刚 51CTO博客，原文链接:http://blog.51cto.com/zyg0227/231860