C语言编程中实现二分查找的简单入门实例
架设有一个数组 v 已经按升序排列了,数组 v 有 n=20 个元素。数组中有个元素 x,如何知道 x 位于该数组的第几位呢? #include <stdio.h> int binsearch(int x,int v[],int n); main() { int i,result,n; int wait; int x = 17; // 需要查找的数值 int v[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); } int binsearch(int x,int n) { int low,high,mid; low = 0; high = n - 1; while (low <= high) { mid = (low + high) / 2; if(x < v[mid]) high = mid - 1; else if (x > v[mid]) low = mid + 1; else return mid; // 看看循环执行了多少次 printf("mid = %d,low = %d,high = %d n",mid,low,high); } return -1; } 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; else begin=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; else current=current->right; } if(back->data>array[i]) back->left=pNew; else back->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); else return find3(root->right,val); } 3、总结 二分查找有非常严格的限制条件(序列必须是有序的); 而使用二分查找树,则会自动创建出"有序树"(中序遍历得到的序列是有序的); 不考虑二叉查找树的建立时间,二者的效率一样,均为O(logn)。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |