二分

二分查找思路很简单，但要把程序写对，却很难，有兴趣的话，可以在网上查一下相关资料，下面给出两种常见的错误：(至于具体错误原因，可以分析程序的执行)

错误程序1：

 1 #include <iostream>
 2 using namespace std;
 3  
 4 int binarySearch(int a[], int n, int key)
 5 {
 6         int low = 0;
 7         int high = n - 1;
 8         int mid;
 9         while(low < high)        //key可能刚好在low与high相等的地方
10         {
11                 mid = (low + high)/2;
12                 if(key == a[mid])
13                         return mid;
14  
15                 if(key < a[mid])
16                         high = mid - 1;
17                 else
18                         low = mid + 1;
19         }
20  
21         return -1;
22 }
23  
24 int main()
25 {
26         int a[] = {0, 1, 2};
27         int n = 3;
28         int key = 0;
29         int result = binarySearch(a, n, key);
30  
31         if(-1 == result)
32                 cout << "no" << endl;
33         else
34                 cout << "yes! location: " << result + 1 << endl;
35  
36         return 0;
37 }

错误程序2：

 1 #include <iostream>
 2 using namespace std;
 3  
 4 int binarySearch(int a[], int n, int key)
 5 {
 6         int low = 0;
 7         int high = n - 1;
 8         int mid;
 9         while(low < high)        //可能是死循环
10         {
11                 mid = (low + high)/2;
12                 if(key == a[mid])
13                         return mid;
14  
15                 if(key < a[mid])
16                         high = mid;
17                 else
18                         low = mid;
19         }
20  
21         return -1;
22 }
23  
24 int main()
25 {
26         int a[] = {0, 1, 2};
27         int n = 3;
28         int key = 100;
29         int result = binarySearch(a, n, key);
30  
31         if(-1 == result)
32                 cout << "no" << endl;
33         else
34                 cout << "yes! location: " << result + 1 << endl;
35  
36         return 0;
37 }

正确程序如下：

#include <iostream>
using namespace std;
 
int binarySearch(int a[], int n, int key)
{
        int low = 0;
        int high = n - 1;
        int mid;
        while(low <= high)
        {
                mid = (low + high)/2;
                if(key == a[mid])
                        return mid;
 
                if(key < a[mid])
                        high = mid - 1;
                else
                        low = mid + 1;
        }
 
        return -1;
}
 
int main()
{
        int a[] = {0, 1, 2};
        int n = 3;
        int key = 0;
        int result = binarySearch(a, n, key);
 
        if(-1 == result)
                cout << "no" << endl;
        else
                cout << "yes! location: " << result + 1 << endl;
 
        return 0;
}