個人認為在編程的時候，我的代碼能力應該是到位的，但是昨天參加的某公司筆試徹底把這個想法給終結了，才意識到自己是多麼的弱。其中印象最深刻的是一道關於二分查找上下界的問題。當時洋洋得意，STL 分分鐘搞定，結果到了面試的時候他要我自己重新實現一下。這個時候就拙計了，拿著筆的我是寫了改改了寫，最後勉強算是完成。
今天反思一下，決定自己再把二分查找重新實現一下。也作為給自己的一個警醒，不要總以為自己能力有多高，總有一天會被打臉的。
一、二分查找思想（參照《算法競賽入門經典》，感謝劉老師）。
在有序表中查找元素常常使用二分查找（Binary Search），有時也譯為折半查找，它的基本思想就像是“猜數字游戲”：你在心裡想一個不超過1000的正整數，我可以保證在10次以內猜到它—–只要你每次告訴我猜的數比你想的大一些、小一些，或者正好猜中。
猜的方法就是二分。首先我猜500，除了運氣特別好正好猜中外，不管你說“太大”還是“太小”，我都可以把可行范圍縮小一半：如果“太大”，那麼答案在1~499之間，那我下一次猜250；如果“太小”，那麼答案在501~1000之間，那我下一次猜750。只要每次選擇可行區間的中間點去猜，每次都可以把范圍縮小一半。由於log21000 < 10，10次內一定能猜到。
二、STL二分查找
在STL中<algorithm>中已經有二分查找的實現了。我在這裡只給簡單的應用，也希望讀者多去了解一下STL的強大。下面的講解參照C++ Reference，有興趣看英文原文的戳鏈接。
1、binary_search()函數
該函數功能是查看某一值在一個已經排好序的序列中是否存在，當存在時返回true，否則返回false。其函數原型如下：
//default (1)
template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last,
const T& val);
//custom (2)
template <class ForwardIterator, class T, class Compare>
bool binary_search (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
注意序列是迭代器表示，原則上可以代入多種數據類型。其中幾個參數如下：
first：序列需要查詢的開始位置；
last：序列需要查詢的結束位置；
val：需要查詢的元素；
comp：用戶自定義比較函數。
注意到default(1)和custom(2)的區別在於用戶有沒有自定義比較函數。對於default(1)版本，使用運算符 “<” 進行元素間的比較；對於custom(2)，使用用戶自定義comp進行元素間比較。
也就是說，binary_search()函數是在序列區間[first, last)中查找是否有某一元素。其中序列一定要先排好序，排序比較函數必須和二分查找比較函數相同。
2、lower_bound()函數
binary_search()只能告訴我們元素在序列中是否存在，卻無法定位它的確切位置。並且有時候所給的序列不一定是每個元素都不同的，同值的元素可能多次出現（因為已經排好序，所以相同的元素是相鄰的）。如果我們需要找到這些相同的元素中的第一個怎麼辦？
其實還STL中還定義了lower_bound()函數來解決這個問題，其函數原型如下：
//default (1)
template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val);
//custom (2)
template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
這個函數的參數和binary_search()函數是相同的，我就不再贅述，但是它的返回類型是ForwardIterator，又見迭代器，為什麼不按照我們的要求返回一個整型值表示下表呢？這個我也不解，不過沒關系，我們照樣能得到我們想要的答案。
也就是說，這個函數的功能是返回迭代器的下界。
確切的說：如果所要查找的元素只有一個，那麼lower_lound()返回了這個元素的地址（注意這裡是地址，不是下標）；
如果所要查找的元素有多個相同，因為他們相鄰，所以可以用一個區間表示[first, last)（左閉右開）它們的位置，那麼lower_bound()函數返回的就是first的地址（再次強調是地址）。
3、upper_bound()函數
舉一反一，我們大概知道upper_bound()函數是干嘛的了吧，那就是返回迭代器上界，也就是所查找元素的區間的上界，但是和lower_bound()略有不同。
其函數原型如下：
//default (1)
template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
const T& val);
//custom (2)
template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
注意我們之前有強調過，表示相同元素的區間[first, last)是左閉右開的，為什麼要這樣子？我不知道，你去問問寫這套STL的人吧，我不敢黑他。這就造成了lower_bound()和upper_bound()的一個不同之處。那就是：lower_bound()可以相等，upper_bound()不能相等。
更加詳細：如果元素只出現一次，那麼lower_bound()找到了這個元素的地址，但是upper_bound()找到的卻是它的下一個；
如果相同元素出現了多次，那麼lower_bound()找到了第一個所找元素的地址，但是upper_bound()找到的卻是最後一個元素的下一個元素的地址。
4、簡單例子測試。
知道上面的三個函數的使用方法了，那麼我們來具體操作一下：
測試代碼如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
int a[] = {0, 0, 2, 2, 2, 4, 4, 4, 4, 5};
int val;
while(1)
{
printf(“請輸入需要查找的數：”);
scanf(“%d”, &val);
if(binary_search(a, a+10, val) == false)
printf(“未找到數 %d，請重新輸入!\n\n”, val);
else
{
printf(“數 %d 已找到!\n”, val);
printf(“相同個數： %d\n”, upper_bound(a, a+10, val)-lower_bound(a, a+10, val));
printf(“下界為： %d\n”, lower_bound(a, a+10, val));
printf(“上界為： %d\n\n”, upper_bound(a, a+10, val));
}
}
return 0;
}
當然上面的是三個函數最簡單的應用了，為了讓大家看得更清楚，讀者不要噴我一個函數寫了多次。我們可以查看所找元素是否存在，它第一次出現的位置和最後一次出現的位置，同時我們看知道了上下界就可以求出該元素出現了多少次。但是，我們看測試結果:
對，我們沒有看錯，這個上下界是地址。就拿2來看，上界減下界等於12，一個int型占用4個字節，那麼2的個數為3個。但是，我們要地址干什麼？沒有用啊！
別著急，想得到下標還不簡單。稍稍修改一下：
printf("下界為： %d\n", lower_bound(a, a+10, val)-a); //減去首地址，就找到了下標位置程序運行結果如圖：
至此，STL二分查找的三個函數大致介紹完成，還有另外的幾個函數讀者有興趣可以上C++ Reference去挖掘一下。
