C语言编程中实现二分查找的简单入门实例
架设有一个数组v已经按升序排列了，数组v有n=20个元素。数组中有个元素x，如何知道x位于该数组的第几位呢？
解决这个问题的一个普遍方法就是二分查找法。下面是程序：
#include<stdio.h>
intbinsearch(intx,intv[],intn);
main()
{
inti,result,n;
intwait;
intx=17;//需要查找的数值
intv[19];//定义一个数组
//给数组赋值
for(i=0;i<20;++i)
v[i]=i;
/**
for(i=0;i<20;++i)
printf("%d\n",v[i]);
*/
n=20;
result=binsearch(x,v,n);
printf("%d",result);
scanf("%d",&wait);
}
intbinsearch(intx,intv[],intn)
{
intlow,high,mid;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(x<v[mid])
high=mid-1;
elseif(x>v[mid])
low=mid+1;
else
returnmid;
//看看循环执行了多少次
printf("mid=%d,low=%d,high=%d\n",mid,low,high);
}
return-1;
}
1、二分查找法
二分查找法有一个很重要的前提条件：即待查找的序列必须是已经排好序的。
假设元素序列是按升序排列，将序列中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将序列分成前、后两个子序列，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子序列，否则进一步查找后一子序列。重复以上过程，直到找到满足条件的记录，查找成功，返回元素在序列中的索引，或直到子序列不存在为止，此时查找失败，返回-1。
intfind2(int*array,intn,intval)
{
if(n<=0)
{
return-1;
}
intbegin=0,end=n-1,mid;
while(begin<=end)
{
mid=(begin+end)/2;
if(array[mid]==val)
returnmid;
elseif(array[mid]>val)
end=mid-1;
else
begin=mid+1;
}
return-1;
}
2、使用二分查找树查找
首先创建一颗二分查找树，我们知道二分查找树的特点是左子树的值都比根节点小，右子树的值都比根节点大，且二分查找树的中序遍历所得到的元素是排好序的。
//二叉查找树数据结构
typedefstructBtree
{
intdata;
Btree*left;
Btree*right;
}*PBTree;
//创建二叉查找树，返回树的根节点
PBTreeCreateBTree(int*array,intn)
{
PBTreeroot=newBtree;
root->data=array[0];
root->left=NULL;
root->right=NULL;
PBTreecurrent,back,pNew;
for(inti=1;i<n;i++)
{
pNew=newBtree;
pNew->data=array[i];
pNew->left=pNew->right=NULL;
current=root;
while(current!=NULL)//找到合适的插入位置
{
back=current;
if(current->data>array[i])
current=current->left;
else
current=current->right;
}
if(back->data>array[i])
back->left=pNew;
else
back->right=pNew;
}
returnroot;
}
//利用二叉查找树进行递归查找
boolfind3(PBTreeroot,intval)
{
if(root==NULL)
returnfalse;
if(root->data==val)
returntrue;
elseif(root->data>val)
returnfind3(root->left,val);
else
returnfind3(root->right,val);
}
3、总结
二分查找有非常严格的限制条件（序列必须是有序的）；
而使用二分查找树，则会自动创建出"有序树"（中序遍历得到的序列是有序的）；
不考虑二叉查找树的建立时间，二者的效率一样，均为O（logn）。