二分查找算法是在有序数组中用到的较为频繁的一种算法，在未接触二分查找算法时，最通用的一种做法是，对数组进行遍历，跟每个元素进行比较，其时间为O(n).但二分查找算法则更优，因为其查找时间为O(lgn)，譬如数组{1， 2， 3， 4， 5， 6， 7， 8， 9}，查找元素6，用二分查找的算法执行的话，其顺序为：
    1.第一步查找中间元素，即5，由于5<6，则6必然在5之后的数组元素中，那么就在{6， 7， 8， 9}中查找，
    2.寻找{6， 7， 8， 9}的中位数，为7，7>6，则6应该在7左边的数组元素中，那么只剩下6，即找到了。

    二分查找算法就是不断将数组进行对半分割，每次拿中间元素和目标元素进行比较。

[cpp] view plaincopy

1. #include <iostream>  
2. using namespace std;  
3.   
4. //初始化数组为有序  
5. bool initArray(int *Array, int arraySize)  
6. {  
7.     for (int i = 0; i != arraySize; ++i)  
8.     {  
9.         Array[i] = i;  
10.     }  
11.     return true;  
12. }  
13.   
14. //递归二分  
15. int binarySearchRecursion(int *Array, int item, int begin, int end)  
16. {  
17.     if ((begin > end) || Array == NULL)  
18.     {  
19.         return -1;  
20.     }  
21.   
22.     int middle = begin + (end - begin)/2;  
23.     if (Array[middle] == item)  
24.     {  
25.         return middle;  
26.     }  
27.     else if (item > Array[middle])  
28.     {  
29.         return binarySearchRecursion(Array,item,middle+1,end);  
30.     }  
31.     else  
32.     {  
33.         return binarySearchRecursion(Array,item,begin,middle-1);  
34.     }  
35.   
36.     return -1;  
37. }  
38.   
39. //循环二分  
40. int binarySearchLoop(int *Array, int item, int begin, int end)  
41. {  
42.     if (Array == NULL)  
43.     {  
44.         return -1;  
45.     }  
46.   
47.     while (begin <= end)  
48.     {  
49.         int middle = begin + (end - begin)/2;  
50.         if (Array[middle] == item)  
51.         {  
52.             return middle;  
53.         }  
54.         else if (item > Array[middle])  
55.         {  
56.             begin = middle + 1;  
57.         }  
58.         else  
59.         {  
60.             end = middle - 1;  
61.         }  
62.     }  
63.   
64.     return -1;  
65. }  
66.   
67.   
68. int main()  
69. {  
70.   
71.     int arraySize = 100;  
72.     int *Array = new int[arraySize];  
73.     initArray(Array,arraySize);  
74.   
75.     /* 
76.     在二分查找中，end应该指向的是数组的最后的一个元素， 
77.     而不是指向最后一个元素的下一个地址， 
78.     因为该元素是可以被二分查找的Middle指针搜索到的，因此传入的值为 
79.     arraySize-1 
80.     */  
81.     cout << binarySearchRecursion(Array,-98,0,arraySize - 1) << endl;  
82.     cout << binarySearchLoop(Array,-56,0,arraySize - 1) << endl;  
83.   
84.   
85.     delete Array;  
86. }