Algo: Binary search
二分查找的基本寫法：
#include <vector>
#include <iostream>
int binarySearch(std::vector<int> coll, int key)
{
int l = 0;
int r = (int)coll.size() - 1;
while (l <= r)
{
int m = l + (r - l) / 2;
if (key == coll[m])
{
return m;
}
if (key > coll[m])
{
l = m + 1;
}
else
{
r = m - 1;
}
}
return -1;
}
int main()
{
int arr[] = { 2, 3, 4, 10, 40 };
std::vector<int> coll(arr, arr + sizeof(arr) / sizeof(arr[0]));
int key = 10;
int index = binarySearch(coll, key);
if (-1 == index)
{
std::cout << "Element is not present in array" << std::endl;
}
else
{
std::cout << "Element is present at index " << index << std::endl;
}
return 0;
} 曆史上，Knuth在其<<Sorting and Searching>>一書的第6.2.1節指出：盡管第一個二分搜尋算法于1946年就出現，然而第一個完全正确的二分搜尋算法直到1962年才出現。
而不經仔細斟酌而寫出的一個二分查找經常遭遇off by one或者無限循環的錯誤。下面将讨論二分查找的理論基礎，實作應用，及如何采用何種技術保證寫出一個正确的二分程式，讓我們免于思考麻煩的邊界及結束判斷問題。
在C++的STL中有如下函數 lower_bound、upper_bound、binary_search、equal_range，這些函數就是我們要考慮如何實作的那些。通過實作這些函數，可以檢查你是否真的掌握了二分查找。
理論基礎：
當我們碰到一個問題，需要判斷它是否可以采用二分查找來解決。對于最一般的數的查找問題，這點很容易判斷，然而對于某些比如可以采用二分+貪心組合，二分解方程，即某些具有單調性的函數問題，也是可以利用二分解決的，然而有時它們表現的不那麼顯然。
考慮一個定義在有序集合S上的斷言，搜尋空間内包含了問題的候選解。在本文中，一個斷言實際上是一個傳回布爾值的二值函數。這個斷言可以用來驗證一個候選解是否是所定義的問題合法的候選解。
我們把下面的一條定理稱之為Main Theorem: Binary search can be used if and only if for all x in S, p(x) implies p(y) for all y > x. 實際上通過這個屬性，我們可以将搜尋空間減半，也就是說如果我們的問題的解應用這樣的一個驗證函數，驗證函數的值可以滿足上述條件，這樣這個問題就可以用二分查找的方法來找到那個合适的解，比如最左側的那個合法解。以上定理還有一個等價的說法 !p(x) implies !p(y) for all y < x 。這個定理很容易證明，這裡省略證明。
實際上如果把這樣的一個p函數應用于整個序列，我們可以得到如下的一個序列
fasle false false ......true true....
如果用01表示，實際上就是如下這樣的一個序列0 0 0 0......1 1 1 1.......
而所有的二分查找問題實際都可以轉化為這樣的一個01序列中第一個1的查找問題，實際上我們就為二分查找找到了一個統一的模型。就像排序網絡中利用的01定理，如果可以對所有的01序列排序，則可以為所有的序列排序。實際上二分查找也可以用來解決true true....fasle false false ......即1 1 1 1...... 0 0 0 0.....序列的查找問題。當然實際如果我們把p的定義變反，這個序列就變成了上面的那個，也就是可以轉化為上面的模型。
這樣我們就把所有問題轉化為求0011模式序列中第一個1出現的位置。當然實際中的問題，也可能是求1100模式序列最後一個1的位置。同時要注意對應這兩種情況下的實作有些許不同，而這個不同對于程式的正确性是很關鍵的。
下面的例子對這兩種情況都有涉及，一般來說具有最大化要求的某些問題，它們的斷言函數往往具有1100模式，比如poj3258 River Hopscotch；而具有最小化要求的某些問題，它們的斷言函數往往具有0011模式，比如poj3273 Monthly Expense。
而對于數key的查找，我們可以利用如下一個斷言使它成為上述模式。比如x是否大于等于key，這樣對于一個上升序列來說它的斷言函數值成為如下模式：0 0 0 0......1 1 1 1.......，而尋找最左邊的key(類似stl中的lower_bound,則就是上述模型中尋找最左邊的1.當然問題是尋找最後出現的那個key(類似stl中的upper_bound),隻需要把斷言修改成：x是否小于等于key，就變成了1 1 1 1...... 0 0 0 0.....序列的查找問題。
可見這樣的查找問題，變成了如何尋找上述序列中的最左或最右的1的問題。
類似的一個單調函數的解的問題，隻要設立一個斷言：函數值是否大于等于0？也變成了如上的序列，如果是單調上升的，則變成了0011模式，反之則是1100模式。實際上當函數的自變量取值為實數時，這樣的一個序列實際上變成了一種無窮數列的形式，也就是1111.....0000中間是無窮的，01的邊界是無限小的。這樣尋找最右側的1，一般是尋找一個近似者，也就是采用對實數域上的二分(下面的源代碼4)，而用fabs(begin-end)來控制精度，确定是否停止疊代。比如poj 3122就是在具有1111.....0000模式的無窮序列中查找那個最右側的1，對應的自變量值。
基本例題
poj 3233 3497 2104 2413 3273 3258 1905 3122
注：
poj1905 實際上解一個超越方程 L"sinx -Lx=0,可以利用源碼4，二分解方程
poj3258 尋找最大的可行距離，實際上是111000序列中尋找最右側的1，可以參考源碼3
poj3273 尋找最小的可行值，實際上是000111序列中尋找最左側的1，可以參考源碼2
總結
1、首先尋找進行二分查找的依據，即符合main 理論的一個斷言：0 0 0 ........111.......
2、确定二分的上下界，盡量的讓上下界松弛，防止漏掉合理的範圍，确定上界，也可以倍增法
3、觀察确定該問題屬于0011還是1100模式的查找
4、寫程式注意兩個不變性的保持
5、注意驗證程式可以處理01這種兩個序列的用例，不會出錯
6、注意mid = begin+(end-begin)/2,用mid=(begin+end)/2是有溢出危險的。實際上早期的java的jdk裡的二分搜尋就有這樣的bug，後來java大師Joshua Bloch發現，才改正的。
對二分查找進行分類：取整方式：向下取整 向上取整 （共2種）區間開閉：閉區間 左閉右開區間 左開右閉區間 開區間 （共4種）問題類型：對于不下降序列a，求最小的i，使得a[i] = key對于不下降序列a，求最大的i，使得a[i] = key對于不下降序列a，求最小的i，使得a[i] > key對于不下降序列a，求最大的i，使得a[i] < key對于不上升序列a，求最小的i，使得a[i] = key對于不上升序列a，求最大的i，使得a[i] = key對于不上升序列a，求最小的i，使得a[i] < key對于不上升序列a，求最大的i，使得a[i] > key（共8種）綜上所述，二分查找共有2*4*8=64種寫法。
重要的是要會寫一種對的。
首先有幾個數字要注意
1、中位數有兩個：
下位中位數：lowerMedian = (length - 2) / 2;
上位中位數：upperMedian = length / 2;
常用的是下位中位數，通用的寫法如下，語言int經常自動向下取整，
median = (length - 1) / 2;
指針的區間當然可以開區間，也可以閉區間，也可以半開半閉。但老老實實兩頭取閉區間總是不會錯。上面的中位數，轉換成兩頭閉區間 [low,high] 就變成下面這樣：
median = low + (high - low) / 2;
2、不要圖快用加法，會溢出，
median = ( low + high ) / 2; // OVERFLOW
3、另外一個關鍵點是“終結條件”
不要以 low == high 做終結條件，會被跳過的。
if (low == high)
{
return (nums[low] >= target)? low : ++low;
} 不相信在 [1, 5] 裡找 0 試試？
正确的終結條件是：
low > high
也就是搜尋空間為空。
滿足終結條件以後，傳回值完全不需要糾結，直接傳回低位 low。
因為回過頭去放慢鏡頭，二分查找的過程就是一個 維護 low 的過程：
low從0起始。隻在中位數遇到确定小于目标數時才前進，并且永不後退。low一直在朝着第一個目标數的位置在逼近。知道最終到達。
至于高位 high，就放心大膽地縮小目标數組的空間吧。
是以最後的代碼非常簡單，
#include <vector>
#include <iostream>
int binarySearch(std::vector<int> coll, int key)
{
int low = 0;
int high = (int)coll.size() - 1;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (key > coll[mid])
{
low = mid + 1;
}
else if (key < coll[mid])
{
high = mid - 1;
}
else
{
return mid;
}
}
return low;
}
int main()
{
int arr[] = { 2, 3, 4, 10, 40 };
std::vector<int> coll(arr, arr + sizeof(arr) / sizeof(arr[0]));
int key = 10;
int index = binarySearch(coll, key);
if (-1 == index)
{
std::cout << "Element is not present in array" << std::endl;
}
else
{
std::cout << "Element is present at index " << index << std::endl;
}
return 0;
} 遞歸版也一樣簡單，
#include <vector>
#include <iostream>
int binarySearchRecur(std::vector<int> coll, int key, int low, int high)
{
if (low > high)
{
return low;
}
int mid = low + (high - low) / 2;
if (key > coll[mid])
{
return binarySearchRecur(coll, key, mid + 1, high);
}
else if (key < coll[mid])
{
return binarySearchRecur(coll, key, low, mid - 1);
}
else
{
return mid;
}
}
int main()
{
int arr[] = { 2, 3, 4, 10, 40 };
std::vector<int> coll(arr, arr + sizeof(arr) / sizeof(arr[0]));
int size = (int)coll.size();
int key = 10;
int index = binarySearchRecur(coll, key, 0, size);
if (-1 == index)
{
std::cout << "Element is not present in array" << std::endl;
}
else
{
std::cout << "Element is present at index " << index << std::endl;
}
return 0;
} 但上面的代碼能正常工作，有一個前提條件：元素空間沒有重複值。
推廣到有重複元素的空間，二分查找問題就變成：
尋找元素第一次出現的位置。
也可以變相了解成另一個問題，對應C++的 lower_bound() 函數，尋找第一個大于等于目标值的元素位置。
但隻要掌握了上面說的二分查找的心法，代碼反而更簡單：
#include <vector>
#include <iostream>
int binarySearch(std::vector<int> coll, int key)
{
int low = 0;
int high = (int)coll.size() - 1;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (key > coll[mid])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return low;
}
int main()
{
int arr[] = { 2, 3, 4, 10, 40 };
std::vector<int> coll(arr, arr + sizeof(arr) / sizeof(arr[0]));
int key = 10;
int index = binarySearch(coll, key);
if (-1 == index)
{
std::cout << "Element is not present in array" << std::endl;
}
else
{
std::cout << "Element is present at index " << index << std::endl;
}
return 0;
} 翻譯成遞歸版也是一樣：
#include <vector>
#include <iostream>
int binarySearchRecur(std::vector<int> coll, int key, int low, int high)
{
if (low > high)
{
return low;
}
int mid = low + (high - low) / 2;
if (key > coll[mid])
{
return binarySearchRecur(coll, key, mid + 1, high);
}
else
{
return binarySearchRecur(coll, key, low, mid - 1);
}
}
int main()
{
int arr[] = { 2, 3, 4, 10, 40 };
std::vector<int> coll(arr, arr + sizeof(arr) / sizeof(arr[0]));
int size = (int)coll.size();
int key = 10;
int index = binarySearchRecur(coll, key, 0, size);
if (-1 == index)
{
std::cout << "Element is not present in array" << std::endl;
}
else
{
std::cout << "Element is present at index " << index << std::endl;
}
return 0;
} 以上代碼均通過leetcode測試。标準銀彈。每天早起寫一遍，鍛煉肌肉。
最後想說，不要怕二分查找難寫，邊界情況複雜。實際情況是，你覺得煩躁，大牛也曾經因為這些煩躁過。一些臭名昭著的問題下面，經常是各種大牛的評論（惡心，變态，F***，等等）。而且這并不考驗什麼邏輯能力，隻是仔細的推演罷了。拿個筆出來寫一寫，算一算不丢人。很多問題徹底搞清楚以後，經常就是豁然開朗，然後以後妥妥舉一反三。以上。
參考：
https://www.zhihu.com/question/36132386
https://en.wikipedia.org/wiki/Binary_search_algorithm
https://www.geeksforgeeks.org/binary-search/
https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/
居天下之廣居，立天下之正位，行天下之大道，得志與民由之，不得志獨行其道，富貴不能淫，貧賤不能移，威武不能屈，此之謂大丈夫。