二分查找

一、普通的二分查找算法：

 1 int BS(int a[], int k, int n)
 2 {
 3     int low = 0;
 4     int high = n - 1;
 5     while (low <= high)
 6     {
 7         int mid = (high - low) / 2 + low;
 8         if (a[mid] == k)
 9             return mid;
10         else
11             if (a[mid] < k)
12                 low = mid + 1;
13             else
14                 high = mid - 1;
15     }
16     return -1;
17 }
18 int main()
19 {
20     int a[] = { 1,1, 3, 6, 8, 9, 9, 10 };
21     cout << BS(a, 0, 8) << endl;
22     system("pause");
23     return 0;
24 }

二、查找关键元素在有序数组中的首次出现位置：

 1 int lowerBoner(int a[], int k,int n)
 2 {
 3     int low = 0;
 4     int high = n - 1;
 5     while (low < high)
 6     {
 7         int mid = (high - low) / 2 + low;
 8         if (a[mid] < k)
 9             low = mid+1;
10         else
11             high = mid;
12     }
13     if (low >= n || a[low] != k)
14         return -1;
15     else
16         return low;
17 }
18 int main()
19 {
20     int a[] = { 1,1, 3, 6, 8, 9, 9, 10 };
21     cout << lowerBoner(a, 9, 7) << endl;
22     system("pause");
23     return 0;
24 }

三、查找关键元素在有序数组中的末次出现位置：

 1 int upperbound(int a[], int k,int n){
 2     int low = 0;
 3     int high = n - 1;
 4     while (low < high){
 5         int mid = low + (high - low + 1) / 2;
 6         if (a[mid] > k){
 7             high = mid - 1;
 8         }
 9         else{
10             low = mid;
11         }
12     }
13     if (low >= n || a[low] != k){
14         return -1;
15     }
16     else{
17         return low;
18     }
19 }
20 
21 int main()
22 {
23     int a[] = { 1,1, 3, 6, 8, 9, 9, 10 };
24     cout << upperbound(a, 1, 8) << endl;
25     system("pause");
26     return 0;
27 }