d732: 二分搜尋法 解題心得

題目連結：https://zerojudge.tw/ShowProblem?problemid=d732

給你一個嚴格遞增的數列A1,A2,A3.....An(1<=n<=100000), &下面有幾個問題的詢問數k(1<=K<=100000),以及k個詢問的整數x,求數列中是否存在一個Ai(1<=i<=n)的值與X相等?

輸入說明

第一行包含兩個整數n,k分別表示數列長度以及詢問數,第二行包含n個整數第i(1<=i<=n)個整數依序為數列中Ai的值,第三行包含k個詢問的整數x. 

輸出說明

對於每個詢問整數x對應一行輸出:

輸出i的值其中1<=i<=n且Ai=x若沒有這樣的i值請輸出0代替.

範例輸入 #1            範例輸出 #1

5 5                            2

1 3 4 7 9                   1

3 1 9 7 -2                  5

                                 4

                                 0

很標準的2元搜尋法，是很好的練習題。

以下附上程式碼，如果有什麼問題請留言或寄信給我囉。

#include <iostream>
using namespace std;

int main()
{
    cin.tie(0), cin.sync_with_stdio(false);
    int n , m;
    cin >> n >> m;
    int* v = new int[n];
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    int a;
    for(int i = 0; i < m; i++) {
        cin >> a;
        int start = 0;
        int end = n;
        int mid = (start + end) >> 1;
        bool find = false;
        while(true) {
            if(v[mid] > a) {
                end = mid;
            } else if(v[mid] < a) {
                start = mid;
            } else {
                find = true;
                break;
            }
            
            if(mid == (end + start) >> 1) break;
            mid = (end + start) >> 1;
            
        }
        find ? cout << mid+1 <<endl : cout << 0 << endl;
    }

    return 0;
}