查找----二分查找法

1、二分查找法

二分查找法有一个很重要的前提条件：即待查找的序列必须是已经排好序的。

假设元素序列是按升序排列，将序列中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将序列分成前、后两个子序列，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子序列，否则进一步查找后一子序列。重复以上过程，直到找到满足条件的记录，查找成功，返回元素在序列中的索引，或直到子序列不存在为止，此时查找失败，返回-1。

代码示例如下：

int find2(int *array,int n,int val){if (n<=0){return -1;}int begin=0,end=n-1,mid;while(begin<=end)            {mid=(begin+end)/2;if (array[mid]==val)return mid;else if(array[mid]>val)end=mid-1;elsebegin=mid+1;}return -1;}

2、使用二分查找树查找

首先创建一颗二分查找树，我们知道二分查找树的特点是左子树的值都比根节点小，右子树的值都比根节点大，且二分查找树的中序遍历所得到的元素是排好序的。

//二叉查找树数据结构typedef struct Btree {int data;Btree *left;Btree *right;}*PBTree;//创建二叉查找树，返回树的根节点PBTree CreateBTree(int *array,int n){PBTree root=new Btree;root->data=array[0];root->left=NULL;root->right=NULL;PBTree current,back,pNew;for (int i=1;i<n;i++){pNew=new Btree;pNew->data=array[i];pNew->left=pNew->right=NULL;current=root;while(current!=NULL)   //找到合适的插入位置{back=current;if(current->data>array[i])current=current->left;elsecurrent=current->right;}if(back->data>array[i])back->left=pNew;elseback->right=pNew;}return root;}//利用二叉查找树进行递归查找bool find3(PBTree root,int val){if (root==NULL)return false;if (root->data==val)return true;else if(root->data>val)return find3(root->left,val);elsereturn find3(root->right,val);}

3、总结

二分查找有非常严格的限制条件（序列必须是有序的）；

而使用二分查找树，则会自动创建出"有序树"（中序遍历得到的序列是有序的）；

不考虑二叉查找树的建立时间，二者的效率一样，均为O（logn）。