二分查找算法C
二分查找也屬於順序表查找范圍，二分查找也稱為折半查找。二分查找(有序)的時間復雜度為O(LogN)。
二分查找的基本思想是， 在有序表中，取中間記錄作為比較對象，若給定值與中間記錄的關鍵字相等，則查找成功；若給定值小於中間記錄的關鍵字，則在中間記錄的左半區繼續查找；若給 定值大於中間記錄的關鍵字，則在中間記錄的右半區繼續查找。不斷重復上述過程，直到找到為止。
從二分查找的定義我們可以看出，使用二分查找有兩個前提條件：
1，待查找的列表必須有序。
2，必須使用線性表的順序存儲結構來存儲數據。
二分法查找在針對大量有序排列的情況下發揮出很優越的效率，這裡以最具規律性的數組為例，代碼如下：
1 #include <stdio.h>
2 //二分查找
3 int binary_search(const int c[], int l,int h,int key);
4 void Display(int x);
5 int a[]={15,8,100,46,22,56,34,79,98,66,200,11,300};
6 int z=sizeof(a)/sizeof(int);
7 int b[sizeof(a)/sizeof(int)];
8 int t;
9 int i;
10 int main(int argc, const char * argv[]) {
11
12 for (i=0; i<(sizeof(a)/sizeof(int)); i++) {
13 b[i]=a[i];
14 }
15 //printf("%ld\n",sizeof(a)/sizeof(int));
16
17 for(i=0;i<(sizeof(a)/sizeof(int));i++)
18 {
19 for(int j=i;j<(sizeof(a)/sizeof(int));j++)
20 {
21 if(b[i]>b[j]) {
22 t=b[i];
23 b[i]=b[j];
24 b[j]=t;
25 }
26 }
27 }
28 printf("\n");
29 int m=0;
30 int n=z;
31 int w;
32 int x;
33 printf("請輸入要查找的整數:");
34 scanf("%d",&x);
35 w=x;
36 // getchar();
37 int g;
38 g=binary_search(b, m, n, w);
39 Display(g);
40 return 0;
41 }
42
43 int binary_search(const int c[], int l,int h, int key){
44 while(l<= h)
45 {
46 int f = (l + h)/2;
47 if(c[f]== key)
48 return c[f] ;
49 //在左半邊
50 else if(c[f] > key)
51 h = f - 1;
52 //在右半邊
53 else
54 l = f + 1;
55 }
56 //沒找到
57 return -1;
58 }
59
60 //打印結果
61 void Display(int x){
62 if (x!=-1) {
63 for(i=0;i<z;i++){
64 if (x==a[i]) {
65 printf("所在位置:%d\n",i);
66 }
67 }
68 }
69
70 else{
71 printf("對不起，沒有找到該數\n");
72 }
73 }
運行結果1：
請輸入要查找的整數:200 所在位置:10 Program ended with exit code: 0
運行結果2：
請輸入要查找的整數:500 對不起，沒有找到該數 Program ended with exit code: 0
