大家有玩過猜數字遊戲嗎？遊戲的規則是這樣的：主持人會在心中默想一個特定範圍的數字、玩家的任務就是要猜出主持人心中想的那個數字。而每當玩家猜一個數字時，主持人就會告訴玩家他想的數字跟玩家猜的數字之間的大小關係。

你會採用什麼樣的策略來猜呢？換句話說，你會如何「搜尋」出答案呢？接下來我們就要來探討幾種關於搜尋的演算法：線性搜尋法與二分搜尋法。

對於剛剛的猜數字遊戲，我們有一種最粗暴的作法：從第一個數字一路猜到最後一個數字，我們總有一天會猜中！而這樣的作法有一個正式的名稱，叫做線性搜尋法，顯然在目標存在的狀況下都不會出錯，那麼效率如何呢？

對於一個長度為 $N$ 的序列，若是我們想要找到裡面的某個元素，由於我們是一個一個找，因此在最糟的情況下會需要將序列中的 $N$ 個元素都檢查過一次，因此時間複雜度為 $O(N)$。非常直覺的作法，只可惜...效率好像有點差強人意。

寫成程式碼大概像這個樣子：

// arr 是我們要搜尋的序列、len 是序列的長度、tar 是我們要搜尋的目標。
// 回傳值為目標的索引值。
int linear_search (int arr[], int len, int tar) {
    for (int i = 0; i < len; ++i) {  // 暴力檢查每個位置
        if (arr[i] == tar) return i;   // 找到答案後直接回傳
    }
    return len;                       // 沒找到，回傳 len。
}

然而我們會發現剛剛的作法根本就沒有用到主持人提供的資訊。因此我們接下來就來看看猜數字遊戲最廣為人知的一種策略，也就是每次都猜一半，舉例來說，假設這次的數字範圍是 0 到 100，我們就會猜中間的數字，也就是 50、此時如果主持人說要再大一點，我們就會挑選 50 與 100 的中間，也就是 75 作為我們的第二次猜測。以此類推，直到猜出答案為止。這樣的作法就是所謂的二分搜尋法。

我們很直覺的會覺得這樣做會比線性搜尋法更好，但究竟好了多少呢？

我們會發現每次猜測之後，可能是答案的範圍就會少一半。舉例來說，一樣是 0 到 100，我們只要猜 50，那麼不管主持人說大於還是小於，可能會是答案的數字範圍都會從 100 個變成 50 個。那麼，對於一個長度為 $N$ 的序列，我們最慘只要猜錯 $\lceil\log_2 N\rceil=O(\log N)$ 次，就會只剩下唯一的答案候選人，而他就會是我們要找的答案。

因此我們得到了 $O(\log N)$ 的複雜度，比線性搜尋法快上不少，既然如此，那為什麼會需要線性搜尋法呢？原因是二分搜的目標序列必須要是有「單調性」，如果序列是雜亂無章的，那就無法從一次猜測的結果來砍半答案的可能範圍，因此我們會需要排序，但某些時候為了一次的搜尋而排序實在是太浪費了，這時候就直接暴力搜尋就可以了！

利用前述的概念，寫出來的二分搜就像這個樣子：

// arr 是我們要搜尋的序列 (由小到大排列好的)、len 是序列的長度、tar 是
// 我們要搜尋的目標。
// 回傳值為目標的索引值。
int bin_search (int arr[], int len, int tar) {
    int l = 0, r = len;         // 答案候選區間 (左閉右開)。

    while (l < r) {
        int m = l + (r - l) / 2;  // 猜中間的。
        if (arr[m] < tar)
            l = m + 1;              // 猜的太小，更新候選區間為右半邊。
        else if (arr[m] > tar)
            r = m;                  // 猜的太大，更新候選區間為左半邊。
        else
            return m;               // 猜中了。
    }

    return len;                 // 沒找到，回傳 len。
}

實做上我們通常會專注於維護可能的答案區間，在這裡要特別注意到邊界的定義，像範例程式碼就是「左閉右開」（包含左邊，但不包含右邊），不同的邊界定義會產生不同的寫法，在實做時需要特別注意。

然而，在大部份的情況下，我們會採用更泛用的作法：找出第一個大於等於目標的位置而非目標的位置，程式碼如下：

// arr 是我們要搜尋的序列 (由小到大排列好的)、len 是序列的長度、tar 是
// 我們要搜尋的目標。
// 回傳值為第一個大於等於目標的索引值。
int lower_bound_bin_search (int arr[], int len, int tar) {
    int l = 0, r = len;         // 左界是不確定狀態。
                                // 右界是保證大於等於 tar。

    while (l < r) {
        int m = l + (r - l) / 2;  // 猜中間的。
        if (arr[m] < tar)
            l = m + 1;              // 猜的太小，更新左界。
        else if (arr[m] >= tar)
            r = m;                  // 猜的太大，更新右界。
    }

    return r;                   // 回傳結果。
}

同樣的，我們也要良好的定義左、右界，範例程式碼中，左界被定義為「不確定是小於還是大於等於的位置」，因此在更新時不能更新為 m（他是確認小於的位置），而程式中止在左右界相同時（也就是不確定大小關係的位置已經不存在了）。

看完前面的內容，應該不難發現二分搜在實做上超級容易出錯，但別擔心，STL 已經幫我們寫好了好用的二分搜函式囉！

• lower_bound(first, last, val, cmp)：從 [first, last) 中找到第一個元素 element 使得 cmp(element, val) 為 false 的位置。
• upper_bound(first, last, val, cmp)：從 [first, last) 中找到第一個元素 element 使得 cmp(val, element) 為 true 的位置。

關於 first 與 last，我們可以傳入一個陣列的兩個位置，也可以利用 STL 容器的 begin() 與 end() 來代表，另外，cmp 的意義與 std::sort() 的 cmp 相同，而傳入的序列必須要以這個 cmp 的規則排序，至於 cmp 的寫法這裡就不再贅述，以下提供一組範例：

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

bool cmp (int a, int b) {
    return a > b;
}

int main () {
    int arr[5] = {1, 3, 3, 5, 8};
    int *lower_pos = lower_bound(arr, arr + 5, 3);
    int *upper_pos = upper_bound(arr, arr + 5, 3);
    cout << "lower_bound of ascending: " << lower_pos - arr << '\n';
    cout << "upper_bound of ascending: " << upper_pos - arr << '\n';

    vector<int> vec = {8, 5, 3, 3, 1};
    auto lo_vec_pos = lower_bound(vec.begin(), vec.end(), 3, cmp);
    auto up_vec_pos = upper_bound(vec.begin(), vec.end(), 3, cmp);
    cout << "lower_bound of descending: " << lo_vec_pos - vec.begin() << '\n';
    cout << "upper_bound of descending: " << up_vec_pos - vec.begin() << '\n';
}

看完了二分搜的寫法，緊接著讓我們來看一下二分搜會如何出現在題目裡吧！

先從我們熟悉的開始看起，也就是在一個序列中進行二分搜：

一開始還看不出這道題目與二分搜有什麼關係，但我們可以立刻想到一個 $O(N^3)$ 的暴力作法，但想當然爾會超時，仔細觀察一下，我們會發現當我們在枚舉其中兩個數字時，第三個數字其實也就已經被定下來了，也就是說，我們只要暴力的窮舉其中兩個數字，然後確認我們需要的第三個數字有幾個就可以了！

那麼，我們要如何計算第三個數字的數量呢？這時候就輪到二分搜上場了！我們只要把所有的數字由小到大排好，然後利用 lower_bound() 就可以找到我們的目標了。然而，單用 lower_bound() 我們只能確認我們的目標是否存在、以及在序列中的哪裡而已，萬一我們的目標數字有好幾個該怎麼辦呢？

這個時候我們就可以利用 upper_bound() 了，lower_bound() 會告訴我們第一個大於等於目標的位置、upper_bound() 則會告訴我們第一個大於目標的位置，將兩者相減，我們就可以得到等於目標的長度、也就是目標數字的個數了！

最後只要注意一些使用到重複數字的細節並加以處理就可以通過這一題囉！

搜尋是個大家常常都會需要的功能，不同的搜尋方法有不同的特色，像是線性搜簡單無腦但慢、二分搜有效率但也有所限制。

其中二分搜雖然是個基礎的演算法，但他非常好用，而「把東西切一半」這樣的想法還會在未來的許多資料結構與演算法之中一而再、再而三的出現，所以希望各位讀者看文本文後可以對二分搜有基本的認識，並準備好面對接下來的挑戰！