C說話編程中完成二分查找的簡略入門實例。本站提示廣大學習愛好者:(C說話編程中完成二分查找的簡略入門實例)文章只能為提供參考,不一定能成為您想要的結果。以下是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 v[], 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)。