架設(shè)有一個(gè)數(shù)組 v 已經(jīng)按升序排列了，數(shù)組 v 有 n=20 個(gè)元素。數(shù)組中有個(gè)元素 x，如何知道 x 位于該數(shù)組的第幾位呢？
解決這個(gè)問題的一個(gè)普遍方法就是二分查找法。下面是程序：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <stdio.h>int binsearch(int x, int v[], int n);main(){ int i, result, n; int wait; int x = 17; // 需要查找的數(shù)值 int v[19]; // 定義一個(gè)數(shù)組 // 給數(shù)組賦值 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; // 看看循環(huán)執(zhí)行了多少次 printf("mid = %d, low = %d, high = %d \n", mid, low, high); } return -1;} |
1、二分查找法
二分查找法有一個(gè)很重要的前提條件：即待查找的序列必須是已經(jīng)排好序的。
假設(shè)元素序列是按升序排列，將序列中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將序列分成前、后兩個(gè)子序列，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子序列，否則進(jìn)一步查找后一子序列。重復(fù)以上過程，直到找到滿足條件的記錄，查找成功，返回元素在序列中的索引，或直到子序列不存在為止，此時(shí)查找失敗，返回-1。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
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、使用二分查找樹查找
首先創(chuàng)建一顆二分查找樹，我們知道二分查找樹的特點(diǎn)是左子樹的值都比根節(jié)點(diǎn)小，右子樹的值都比根節(jié)點(diǎn)大，且二分查找樹的中序遍歷所得到的元素是排好序的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
//二叉查找樹數(shù)據(jù)結(jié)構(gòu) typedef struct Btree { int data; Btree *left; Btree *right; }*PBTree; //創(chuàng)建二叉查找樹，返回樹的根節(jié)點(diǎn) 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; } //利用二叉查找樹進(jìn)行遞歸查找 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、總結(jié)
二分查找有非常嚴(yán)格的限制條件（序列必須是有序的）；
而使用二分查找樹，則會(huì)自動(dòng)創(chuàng)建出"有序樹"（中序遍歷得到的序列是有序的）；
不考慮二叉查找樹的建立時(shí)間，二者的效率一樣，均為O（logn）。
