二分法查找
1: // binary search of an integer array, this search is efficient for large arrays
2: // tested with PellesC vegaseat 24jan2005
3:
4: #include <stdio.h>
5:
6: int main()
7: {
8: int a[20] = {0};
9: int n, i, j, temp;
10: int *beg, *end, *mid, target;
11:
12: printf(" enter the total integers you want to enter (make it less then 20):\n");
13: scanf("%d", &n);
14: if (n >= 20) return 0; // ouch!
15: printf(" enter the integer array elements:\n" );
16: for(i = 0; i < n; i++)
17: {
18: scanf("%d", &a[i]);
19: }
20:
21: // sort the loaded array, a must for binary search!
22: // you can apply qsort or other algorithms here
23: for(i = 0; i < n-1; i++)
24: {
25: for(j = 0; j < n-i-1; j++)
26: {
27: if (a[j+1] < a[j])
28: {
29: temp = a[j];
30: a[j] = a[j+1];
31: a[j+1] = temp;
32: }
33: }
34: }
35: printf(" the sorted numbers are:");
36: for(i = 0; i < n; i++)
37: {
38: printf("%d ", a[i]);
39: }
40:
41: // point to beginning and end of the array
42: beg = &a[0];
43: end = &a[n]; // use n = one element past the loaded array!
44: printf("\n beg points to address %d and end to %d",beg, end); // test
45:
46: // mid should point somewhere in the middle of these addresses
47: mid = beg += n/2;
48: printf("\n mid points to address %d", mid); // test
49:
50: printf("\n enter the number to be searched:");
51: scanf("%d",&target);
52:
53: // binary search, there is an AND in the middle of while()!!!
54: while((beg <= end) && (*mid != target))
55: {
56: // is the target in lower or upper half?
57: if (target < *mid)
58: {
59: end = mid - 1; // new end
60: n = n/2;
61: mid = beg += n/2; // new middle
62: }
63: else
64: {
65: beg = mid + 1; // new beginning
66: n = n/2;
67: mid = beg += n/2; // new middle
68: }
69: }
70:
71: // did you find the target?
72: if (*mid == target)
73: {
74: printf("\n %d found!", target);
75: }
76: else
77: {
78: printf("\n %d not found!", target);
79: }
80:
81: getchar(); // trap enter
82: getchar(); // wait
83: return 0;
84: }
85:
