章節2-1.搜尋演算法

線性搜尋

線性搜尋是一種簡單的搜尋演算法。逐一檢查搜尋範圍的每個元素，直到找到目標元素或檢查完整個列表。如果有找到目標元素，可以同時得到其位置；如果沒有找到，則表示目標元素不在列表中。
而其實作方式非常簡單，使用for迴圈依序檢查指定範圍即可，請看以下範例。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[8]={3,8,4,1,9,7,6,3};
    int goal;
    cin>>goal;
    for(int i=0;i<8;i++){
        if(a[i]==goal){//若找到目標
            cout<<"found "<<goal<<" at index "<<i<<'\n';//輸出其位置
            break;//跳出迴圈
        }
        if(i==7)cout<<"not found\n";//若i為7但還沒跳出迴圈，代表都沒找到，且這是最後一次迴圈，輸出沒找到
    }
    //若輸入「9」會輸出「found 9 at index 4」
    //若輸入「5」會輸出「not found」
    //若輸入「3」會輸出「found 3 at index 0」
    //假設出現多次的情況我們要其最後出現的位置，可以將迴圈改為for(int i=7;i>=0;i--)，此時輸入「3」會輸出「found 3 at index 7」
}

透過線性搜尋的名稱跟其過程應該很容易了解其複雜度為O(n)，儘管最好情況可能O(1)直接找到目標，但最壞情況全部找完或目標出現在隨機位置的複雜度都還是O(n)。

二分搜尋

二分搜尋是一種高效的搜尋算法，用於在一個已排序的列表中查找目標元素。
二分搜尋的基本思想是每次將列表分成兩半，並逐步縮小搜尋範圍。
每次比較範圍正中間的元素與目標元素，假設列表為由小到大的升冪排序，如果目標元素小於中間元素，就在左半部分繼續搜尋；如果目標元素大於中間元素，就在右半部分繼續搜尋。這樣的過程重複進行，直到找到目標元素或範圍縮小為零。

註:為了便於理解，以下所講的範圍皆為閉區間，即範圍[l,r]會包含l與r。

假設有一個已排序的數列：「1,3,4,8,9」，我們想找出數字4的位置。

若是找數字8。

可以發現以上過程在正中間元素無法剛好找出時，直接利用範圍頭尾索引相加/2無條件捨去即可，但假如使用無條件進位也可以正常運行，此時比較中間元素(9，原索引4)與目標元素(8)，會對左半邊繼續搜尋，即範圍「8」(對應原索引[3,3])，仍能找到正確結果。

若是找數字2。

將以上過程實作為程式就是最基礎的二分搜了，如以下範例。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[8]={1,3,5,7,9,11,13,15};
    int goal;
    cin>>goal;
    //以上為宣告範例陣列與輸入目標，以下開始正式實作二分搜尋
    int l=0,r=7;//l、r分別代表當前範圍左右邊界，此範例之區間為閉區間，要搜尋的範圍為[l,r]，也就是包含l與r
    int ans=-1;//ans為儲存找到位置的變數，初始化為-1可以在沒找到時直接判斷值為-1
    while(l<=r){//此條件代表區間仍至少有一個元素，若不符合代表所有範圍皆已排除
        int mid=(l+r)/2;//如上述的取中間元素索引值過程
        if(a[mid]==goal){//找到元素，紀錄結果並跳出迴圈
            ans=mid;
            break;
        }
        if(a[mid]<goal)l=mid+1;//中間元素小於目標元素，在右半部繼續搜尋，由於mid已經排除，故可以直接將左邊界設為mid+1
        else r=mid-1;//中間元素大於目標元素，在左半部繼續搜尋，由於mid已經排除，故可以直接將右邊界設為mid-1
    }
    if(ans!=-1)cout<<"found "<<goal<<" at index "<<ans;
    else cout<<"not found";
}

由其過程每次會將剩下的範圍切成一半，因此剩餘範圍會是每次範圍/2，搜尋進行最久的情況是跑到範圍為0，因此最多進行的次數就是看最初的範圍大小/2幾次會變0，假設最初範圍大小為n，由數學中log的定義可以知道其值約為「log₂ n」次，又log₂ n=log n/log 2，可以將1/log 2視為log n項的係數，故計算複雜度時將迴圈執行次數視為log n即可，而由於每次切半、判斷中間元素與目標元素皆為O(1)，因此整個迴圈的複雜度為O(log n)。
註:但建議估算O(log n)複雜度演算法的運算次數時仍以log₂ n估計會比較準。

比較線性搜尋與二分搜尋的複雜度，線性搜尋可以直接單次O(n)，二分搜尋需要排序好的數列，若需要排序會先有O(n log n)(關於排序的複雜度可以先回想STL的sort，詳細解釋在下個章節)，然後單次搜尋為O(log n)。
可以發現如果數列沒有排序過，要進行單次搜尋使用線性搜尋的效率較高為O(n)，排序後再二分搜尋為O(n log n)+O(log n)=O(n log n)。
但假設數列沒有排序過，但要進行m次查詢，此時使用線性搜尋的複雜度為O(nm)，排序後再二分搜尋為O(n log n)+O(m log n)=O((n+m)log n)，假設n、m數量級接近則二分搜尋會比線性搜尋快上許多，如n=m=10⁶，帶入得到nm=10¹²，(n+m)log₂ n=2*10⁶*20=4*10⁷。

二分搜尋pro

另外二分搜尋也能實作成更進階的版本，如找到大於等於特定值的最小值，也就是內建lower_bound函式的功能，做法大致相同，只不過需要注意三個重點，一是重新定義目前搜尋範圍的意義，二是改變邊界的方式，三是注意會不會卡在小範圍的情況無法結束。

以lower_bound為例，首先需要重新定義搜尋範圍的意義，上述的二分搜尋中，搜尋範圍的意義是「要搜尋的值可能出現的範圍」，但lower_bound中由於尋找目標變成大於等於特定值的最小值，因此搜尋範圍定義為「大於等於特定值的最小值可能出現的範圍」。
接著可以透過自己模擬搜尋的過程來思考如何改變邊界，在「1,3,5,7,9」(索引值[0,4])要找到大於等於4的最小值，最初會先取索引2的中間元素(數字5)，其符合大於等於4的條件，此時要往左半邊搜尋，因為數字5已經符合條件，右半邊不會再有大於等於4的「最小值」，但此時右邊界不能直接設為mid-1也就是1，因為索引值為2的數字5可能是符合條件的「最小值」，要將右邊界設為mid也就是2，接著對「1,3,5」(索引值[0,2])繼續，由於索引值1的數字3不符合，可以排除中間元素與左半邊，故右邊界可以設為mid+1即3，接著範圍剩下[3,3]，因為此處實作的過程會排除「小於特定值」跟「大於等於特定值但非最小的值」，所以範圍剩1時就是找到答案可以停止搜尋，只不過最後會需要判斷這個值是否真的符合條件，原因在下一段解釋。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[105],n,goal;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    cin>>goal;
    int l=0,r=n-1;
    while(l<r){
        int mid=(l+r)/2;
        if(a[mid]>=goal)r=mid;
        else l=mid+1;
    }
    if(a[l]>=goal)cout<<"found "<<a[l]<<" at index "<<l;
    else cout<<"not found";
}

接著看在「1 3 5」中找大於等於10的最小值的範例，可以發現第一輪取中間元素3(索引值1)後，剩下的範圍就是「5」(索引值[2,2])了，此時若依照上述的執行方式等範圍剩1時就結束，會得到答案「5」，但顯然這是錯誤的，因此可以發現我們的做法在沒有符合條件的值時，會持續向右直到剩下最大的元素，因此還需要再對最終結果進行判斷確認才行。
註:當然有其他方式可以處理，如事先判斷、將右區間之初始值+1，但這邊介紹相對通用的方法。

最後還有一個範例用來解說上面提到的第三個重點，假設今天一樣是由小排到大，但要找小於等於特定值的最大值，一樣將搜尋範圍的定義改成「小於等於特定值的最大值可能出現的範圍」，然後跟上面的概念一樣，如果中間元素符合條件則l=mid(因中間元素可能是答案，但左半邊不會比中間元素大)，否則r=mid-1。此時假設要從「1 5」(索引值[0,1])中找到小於等於3的最大值，直接用上述執行方式會變成，找mid=(0+1)/2=0，數字1(索引值0)符合條件，l=0，然後你就會發現沒完沒了，這就是所謂在小範圍無法停止，原因是我們在範圍無法剛好找到鄭中間元素時使用(l+r)/2無條件捨去來取中間，此時其實會是偏左的元素，然後左邊界的改變方式又剛好是l=mid，此時就可能發生一直將mid取l的無限循環，解決這個問題的最快方式是將中間元素的取法改成取靠右的，也就是無條件進位，直接寫(l+r+1)/2就可以了。
總之就是注意僅剩兩個元素時，中間元素不要取到不會縮小的那個邊界。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[105],n,goal;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    cin>>goal;
    int l=0,r=n-1;
    while(l<r){
        int mid=(l+r)/2;
        if(a[mid]<goal)l=mid;
        else r=mid-1;
    }
    if(a[l]<goal)cout<<"found "<<a[l]<<" at index "<<l;
    else cout<<"not found";
}

也許到這裡有人會想為何不用STL的內建二分搜尋就好？筆者的建議是沒錯，如果只是簡單的在範圍中找lower_bound、upper_bound的確直接使用內建函式就好了，這也是筆者將STL的學習順序擺在前面的關係，先學會高效率、簡單的方法，再詳細解釋(相比之下過去看到的不少教學會先介紹基礎算法實作再介紹STL)。不過筆者認為瞭解背後原理仍是十分重要的，尤其在很多情況下是需要利用這些概念而非簡單的使用函式就能達到目標。

對答案二分搜尋

在很多情況下，進行二分搜尋並非只是在給定數列中找值，而是要利用二分搜尋解決特定問題。
例如:今天我心裡想一個1~1000的數，你可以猜10次，我會告訴你答案大於、小於或等於你猜的數，要怎麼成功猜到我想的數呢？
既然都放在二分搜尋的章節講了，想必就是用二分搜尋先猜中間的數，然後知道大於小於後再縮小可能的範圍繼續執行。
以上的過程，我們並非在給定的數列中尋找一個數，而是在一個範圍的可能性中尋找答案，就稱作對答案二分搜。

如果看到這裡還是有些迷茫的話，沒關係，以下會再舉一些例子，但在這之前，先解釋對答案二分搜十分重要的先決條件「單調性」。
如果上網搜尋「單調性」的話，可以得到單調函數這個結果，所謂單調函數是指數學上的函數，在某個區間內符合遞增或遞減，不一定要嚴格。
這時也許有人會好奇，那上面的例子跟單調性有什麼關係呢，如果我們把上面的例子換成數學函數f(x)，若x>我心中的數則f(x)=1，若x=我心中的數則f(x)=0，若x<我心中的數則f(x)=-1，將圖形畫出來後確實是一個遞增函數沒錯吧！
考慮到二分搜正是用這樣的概念下去搜尋的，若f(x)遞增，那x對應的f(x)如果太小，比x再小的值也一定不符合需求。
如此來看對答案二分搜應該會好理解很多。

接著這邊介紹對答案二分搜尋中相當常見的題目。
先講與二分搜尋無關的版本，假設要做n個一樣的商品，有m台機器可以做，每台機器做一個商品需要花費一天，那麼需要幾天才能完成n個商品呢？
顯然答案會是n/m無條件進位。之所以要先講這個不用二分搜的版本是要強調，令「可以做的商品數」=f(花費天數)，顯然函數f是遞增的，我們的目標就是找出讓f(x)>=n的最小x。
加入二分搜的版本為，要做n個一樣的商品，有m台機器可以做，每台機器做一個商品分別需要花費t₁,t₂,...,t_m天，那麼需要幾天才能完成n個商品呢？
考慮到花費越多時間，可以做的商品數只會更多，因此顯然該函式也是遞增的，因此就可以透過嘗試「花費天數」也就是答案，來看符不符合題目要求，再利用上述對答案二分搜的方法找出符合的最小值就可以了
每嘗試一個答案ans，需要加總ans/t_i(無條件捨去)，複雜度O(m)，然後由於最初答案可能的範圍是[1,n]，因此對該區間二分搜會產生O(log n)的二分搜迴圈，總體的複雜度為O(m log n)，比起原先暴力嘗試答案的O(nm)好上許多