二分搜索及其變體技术頭條網

二分搜索及其變體

二分搜索是一個效率很高的算法。一個良好實現的二分搜索算法，其時間複雜度可以達到 Θ(logn)

Θ(log⁡n)，而空間複雜度只有 O(1)

O(1)。特別地，二分搜索算法的描述十分簡潔。作為程序員，總是喜歡 clean and powerful 的東西。因此，二分搜索無疑對程序員有巨大的吸引力。

按照 Knuth 的說法，「儘管第一個二分搜索算法早在1946年就被髮表，但第一個沒有bug的二分搜索算法卻是在12年後才被髮表出來」。

此篇我們討論二分搜索算法的原理及其各種變體的實現。

算法描述

二分搜索是針對支持隨機訪問的有序數據集進行查找操作的算法。最基本的二分搜索，查找的是等於目標元素的元素在數據集中的位置。它的描述十分簡單：

折半取中，判斷元素與目標元素的大小關係
小於——往前繼續折半

大於——往後繼續折半
等於——返回

此處要注意二分搜索的適用場景：

依賴順序表結構
數據本身必須有序
數據量相對比較元素的開銷要足夠大——不然遍歷即可
數據量相對內存空間不能太大——不然順序表裝不下

二分搜索的實現

複製

#include <iterator>
#include <functional>
template <typename> typename ValueT = typename std::iterator_traits<itert>::value_type,
 typename Compare = std::less<valuet>>
IterT bsearch(IterT first,
 IterT last,
 ValueT target,
 Compare comp = Compare()) {
 IterT result = last;
 while (std::distance(first, last) > 0) {
 IterT mid = first + std::distance(first, last) / 2;
 if (comp(*mid, target)) {
 first = mid + 1;
 } else if (comp(target, *mid)) {
 last = mid;
 } else { // equal 

 result = mid;
 break;
 }
 }
 return result;
}
/<valuet>/<itert>/<typename>/<functional>/<iterator>

這一實現有一些技巧值得說一說。

首先，搜索範圍是由 first 和 last 構成的左閉右開區間。在編程中，堅持使用左閉右開區間，能夠避免大多數索引越界的問題。這是個好習慣，值得一說。

其次，這一實現以 mid = low + (high - low) / 2 的方式來確定折半點。與之相對，還有一種寫法是 mid = (low + high) / 2。在數學的角度，這兩種寫法完全相同。但是在計算機的角度，後者可能涉及到整數的溢出。因此，為了避免溢出，我們應當優先採用實現當中的寫法。

最後，這一實現以 while 循環替代遞歸，節省了函數的遞歸調用帶來的開銷。與之搭配，在未能找到目標時，通過調整區間首尾實現折半動作。這種實現方式是處於效率的考量。

二分搜索的變體

單就查找等於目標的元素來說，這一任務還有哈希表和查找樹等數據結構能高效地完成。相較二分搜索，它們的限制更少——不需要數據集本身有序，也不需要分配連續的大塊內存。如此看來，二分搜索似乎只是看起來美好，實際用途應該不廣。

但事實上，二分搜索還有若干變體。這些變體實現的功能，上述這些數據結構通常很難以較低的時間複雜度完成。這些變體才是最能體現二分搜索威力的場景。這裡介紹常見的四個變體：

查找支持隨機訪問的有序數據集中，第一個等於給定值的元素
查找支持隨機訪問的有序數據集中，最後一個等於給定值的元素
查找支持隨機訪問的有序數據集中，第一個不小於給定值的元素
查找支持隨機訪問的有序數據集中，最後一個不大於給定值的元素

這些變體的實現也不難。在上述標準二分搜索的基礎上，只需要稍加改造即可。需要關注的核心點，就是在不同條件下，區間的首尾應該如何變化。以下是我以 C++ 實現的這些變體。這份實現裡值得一提的地方，在基礎款的二分搜索實現中已經提過，便不再贅述。

複製

#include <iterator>
#include <functional>
enum class BsearchPolicy { UNSPECIFIED, FIRST, LAST, FIRST_NOT_LESS, LAST_NOT_GREATER };
template <typename> typename ValueT = typename std::iterator_traits<itert>::value_type,
 typename Compare>
IterT bsearch(IterT first,
 IterT last,
 ValueT target,
 Compare comp,
 BsearchPolicy policy = BsearchPolicy::UNSPECIFIED) {
 IterT result = last;
 while (std::distance(first, last) > 0) {
 IterT mid = first + std::distance(first, last) / 2;
 if (policy == BsearchPolicy::FIRST_NOT_LESS) {
 if (!comp(*mid, target)) {
 if (mid == first or comp(*(mid - 1), target)) {
 result = mid;
 break;
 } else {
 last = mid;
 }
 } else {
 first = mid + 1;
 }
 } else if (policy == BsearchPolicy::LAST_NOT_GREATER) {
 if (comp(target, *mid)) {
 last = mid;
 } else {
 if (std::distance(mid, last) == 1 or comp(target, *(mid + 1))) {
 result = mid;
 break;
 } else {
 first = mid + 1;
 }
 }
 } else { // policy == UNSPECIFIED or FIRST or LAST
 if (comp(*mid, target)) {
 first = mid + 1;
 } else if (comp(target, *mid)) {
 last = mid;
 } else { // equal
 if (policy == BsearchPolicy::FIRST) {
 if (mid == first or comp(*(mid - 1), *mid)) {
 result = mid;
 break;
 } else {
 last = mid;
 }
 } else if (policy == BsearchPolicy::LAST) {
 if (std::distance(mid, last) == 1 or comp(*mid, *(mid + 1))) { 

 result = mid;
 break;
 } else {
 first = mid + 1;
 }
 } else {
 result = mid;
 break;
 }
 }
 }
 }
 return result;
}
template <typename> typename ValueT = typename std::iterator_traits<itert>::value_type,
 typename Compare = std::less<valuet>>
IterT bsearch(IterT first,
 IterT last,
 ValueT target,
 BsearchPolicy policy = BsearchPolicy::UNSPECIFIED) {
 return bsearch(first, last, target, Compare(), policy);
}
/<valuet>/<itert>/<typename>/<itert>/<typename>/<functional>/<iterator>