參考C++ Refference：
http://www.cplusplus.com/reference/algorithm/lower_bound/
本文前面是函數(shù)原型盒揉， 后面是怎么用
lower_bound()：
默認版本
template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val);
自定義比較函數(shù)版
template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
第一個first參數(shù)是一段連續(xù)空間的首地址摹迷，last是連續(xù)空間末端的地址，val是要查找的值。調(diào)用lower_bound()的前提是這段連續(xù)的空間里的元素是有序（遞增）的胎许。
然后lower_bound()的返回值是第一個大于等于val的值的地址奈辰，用這個地址減去first栏妖，得到的就是第一個大于等于val的值的下標
在自定義版本里有一個comp參數(shù)，它的用處在于奖恰，當你要查找的不是基本數(shù)據(jù)類型吊趾，而是自己定義的struct時就需要自己定義一下，怎么比較兩個struct的大小瑟啃。
用法示例
默認版本
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char *argv[]){
int a[] = {1, 3, 5, 7, 9};
cout << (lower_bound(a, a + 5, 1) - a) << endl;
// 第一個大于等于1的元素是1论泛，下標是0
cout << (lower_bound(a, a + 5, 2) - a) << endl;
// 第一個大于等于2的元素是3，下標是1
cout << (lower_bound(a, a + 5, 8) - a) << endl;
// 第一個大于等于8的元素是9蛹屿，下標是4
cout << (lower_bound(a, a + 5, 100) - a) << endl;
// 最大的元素也不比100大屁奏，故返回值是last，再減a也就是5
}
自定義版本
#include <iostream>
#include <algorithm>
using namespace std;
struct point{
point(){
}
point(int _x, int _y){
x = _x;
y = _y;
}
int x;
int y;
};
bool cmp(point a, point b){
return a.x < b.x;
}
int main(int argc, char *argv[]){
point a[5];
a[0].x = 1;
a[0].y = 100;
a[1].x = 100;
a[1].y = 1;
a[2].x = 30;
a[2].y = 50;
a[3].x = 25;
a[3].y = 120;
a[4].x = 301;
a[4].y = 103;
// 隨便賦值
sort(a, a + 5, cmp);
// 先排序
for (int i = 0; i < 5; i++){
printf("a[%d].x = %d, a[%d].y = %d\n", i, a[i].x, i, a[i].y);
}
// 輸出會發(fā)現(xiàn)他們按照x從小到大排序了
cout << (lower_bound(a, a + 5, point(1, 1000), cmp) - a) << endl;
// 第一個x值大于1的元素是(1, 100)這個元素错负，它的下標為0
cout << (lower_bound(a, a + 5, point(101, 1000), cmp) - a) << endl;
// 第一個x值大于101的元素是(301, 103)這個元素坟瓢，它的下標為4
cout << (lower_bound(a, a + 5, point(1000, 1000), cmp) - a) << endl;
// 因為找不到所以返回a + 5，再減a就是5
}
upper_bound()
用法跟lower_bound()一樣犹撒，只不過它返回的是第一個大于x的值的地址折联， 而lower_bound()是返回第一個大于等于x的值的地址，> 和 >= 是二者的區(qū)別
示例
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char *argv[]){
int a[] = {1, 3, 5, 7, 9};
cout << (upper_bound(a, a + 5, 1) - a) << endl;
// 第一個大于1的元素是3油航，下標是1
cout << (upper_bound(a, a + 5, 2) - a) << endl;
// 第一個大于2的元素是3崭庸，下標是1
cout << (upper_bound(a, a + 5, 7) - a) << endl;
// 第一個大于7的元素是9，下標是4
cout << (upper_bound(a, a + 5, 100) - a) << endl;
// 最大的元素也不比100大谊囚，故返回值是last怕享，再減a也就是5
}
如果要求第一個小于x的數(shù)，或者第一個小于等于x的數(shù)怎么辦呢镰踏？
還是用上面兩個函數(shù)就可以了
查找第一個小于等于x的數(shù)（注：這里的意思為小于x的數(shù)里最大的那個）
算法：upper_bound()的返回值 - 1函筋，就是要查找的地址
比如數(shù)組是int a[] = {1, 3, 5, 7, 9}要查找的數(shù)x是3
用upper_bound()找到的是第一個大于3的數(shù)對吧，它的返回值是5的地址奠伪，把返回結(jié)果再減1就好了跌帐，就是3的地址了。第一個小于等于3的元素是3绊率，沒錯吧谨敛！
這是剛好數(shù)組里有x的情況，那如果沒有呢滤否？比如要查找的元素是4脸狸，那upper_bound()的返回值是5的地址，再減1，就是3的地址了炊甲，第一個小于等于
4的元素是3泥彤，沒錯吧！
那如果查的元素比第一個元素還要小呢卿啡，比如-1吟吝，那upper_bound()的返回值是a，再減1就是a的前一個單元了颈娜。所以這里得特判了剑逃，要不然段錯誤了。
查找第一個小于x的數(shù)
算法：lower_bound()的返回值 - 1官辽，就是要查找的地址
還是用上面的數(shù)據(jù)為例子
要查找的元素為7炕贵，lower_bound的返回值為7的地址，再減一就是5的地址野崇，第一個小于7的元素是5，沒錯亩钟。
要查找8呢乓梨，lower_bound()返回的是9的地址，再減一就是7清酥，沒錯扶镀。
查找-1，lower_bound()返回1的地址焰轻，也就是a臭觉，再減一為a的前一個單元，會越界辱志，需要特判蝠筑。
附：自己寫的lower_bound版本
注意：我的下標從1開始，然后一定要注意揩懒，初始l = 1, r = n + 1什乙，也就是說[l, r)是個左閉右開區(qū)間，r是沒有訪問元素的
ll是long long已球，代碼前面有typedef臣镣，競賽寫習慣了
ll lower_bound(ll *a, ll x, ll n){
ll l = 1, r = n + 1;
while (l < r){
ll mid = (l + r) / 2;
if (x > a[mid]){
l = mid + 1;
}
else if (x < a[mid]){
r = mid;
}
else{
return mid;
}
}
return l;
}
