二分

二分查找：

　　写完二分专题后就没有系统的学习过二分了，导致很长一段时间里我的二分都是写下来后修修改改才过的，这次系统性地写下来。话说二分可是有64中解法呢！ @、@！

对于不下降序列a，n为序列a元素的个数，key为关键字：

1.求最小的i，使得a[i] = key，若不存在，则返回-1

 1 int binary_search_1(int a[], int n, int key)
 2 {
 3     int m, l = 0, r = n - 1;//闭区间[0, n - 1]
 4     while (l < r)
 5     {
 6         m = l + ((r - l) >> 1);//向下取整
 7         if (a[m] < key) l = m + 1;
 8         else r = m;
 9     }
10     if (a[r] == key) return r;
11     return -1;
12 }

2.求最大的i，使得a[i] = key，若不存在，则返回-1

 1 int binary_search_2(int a[], int n, int key)
 2 {
 3     int m, l = 0, r = n - 1;//闭区间[0, n - 1]
 4     while (l < r)
 5     {
 6         m = l + ((r + 1 - l) >> 1);//向上取整
 7         if (a[m] <= key) l = m;
 8         else r = m - 1;
 9     }
10     if (a[l] == key) return l;
11     return -1;
12 }

3.求最小的i，使得a[i] > key，若不存在，则返回-1

 1 int binary_search_3(int a[], int n, int key)
 2 {
 3     int m, l = 0, r = n - 1;//闭区间[0, n - 1]
 4     while (l < r)
 5     {
 6         m = l + ((r - l) >> 1);//向下取整
 7         if (a[m] <= key) l = m + 1;
 8         else r = m;
 9     }
10     if (a[r] > key) return r;
11     return -1;
12 }

4.求最大的i，使得a[i] < key，若不存在，则返回-1

 1 int binary_search_4(int a[], int n, int key)
 2 {
 3     int m, l = 0, r = n - 1;//闭区间[0, n - 1]
 4     while (l < r)
 5     {
 6         m = l + ((r + 1 - l) >> 1);//向上取整
 7         if (a[m] < key) l = m;
 8         else r = m - 1;
 9     }
10     if (a[l] < key) return l;
11     return -1;
12 }

转载自：二分的64中解法！