【答案解析】二分查找法也称为折半查找法，它的思想是每次都与序列的中间元素进行比较。二分查找的一个前提条件是数组是有序的，假设数组array为递增序列，findData为要查找的数，n为数组长度，首先将n个元素分成个数大致相同的两半，取array[n/2]与将要查找的值findData进行比较，如果findData等于array[n/2]，则找到fmdData，算法终止；如果findData＜array[n/2]，则只要在数组array的左半部分继续搜索findData；如果findData＞array[n/2]，则只需要在数组array的右半部分继续搜索即可。
二分查找可以使用递归和非递归的方法来解决，以下是示例代码：
#include＜stdio.h＞
∥非递归算法，如果存在返回数组位置，不存在则返回-1
int BinarySeareh(int array[],int len, int findData)
{
if(array==NULL‖len＜=0)
return -1;
hat start=0;
int end=len-1;
while(start＜=end)
{
int mid=start+(end-start)/2;
if(array[mid]==findData)
return mid;
else if(findData＜array [mid] )
end=mid-1;
else
start=mid+1;
}
return -1;
}
int BinarySearchRecursion(int array[],int findData, int start,int end)
{
if(start＞end)
return -1;
int mid=start+(end-start)/2;
if(array[mid]==findData)
return mid;
else if(findData＜array[mid])
return BinarySearchRecursion(array,findData, start,mid-1);
else
return BinarySearchRecursion(array,findData,mid+1 ,end);
int BinarySearchRecursion(int array[],int len,int findData)
{
if(array==NULL‖len＜=0)
return -1;
return BinaryS earchRecursion(array,findData,0,len-1);
}
int main()
{
int array[]={1,2,3,4,5,6,7,8};
int len=sizeof(array)/sizeof(int);
int index=BinarySearch(array,len,4);
int index2=BinarySearchRecursion(array,len,9);
print f("%d/n%d/n",index,index2);
return 0;
}
程序输出结果：
3
-1
需要注意的是，二分查找算法的时间复杂度为O(logn)，最坏情况下的时间复杂度为O(logn)。