【解題】Zerojudge d732: 二分搜尋法

發布於 更新於 分類於 ， 閱讀次數： 文章字數： 199 所需閱讀時間 ≈ 1 分鐘

題目連結

d732: 二分搜尋法

我的想法

純純的二分搜尋

範例：找 8

1
2
3
1 2 3 4 5 6 7 8 9
↑       ↑       ↑
l       m       r

5 < 8 所以左邊往中點 +1 移動

1
2
3
1 2 3 4 5 6 7 8 9
          ↑ ↑   ↑
          l m   r

7 < 8 所以左邊往中點 +1 移動

1
2
3
4
1 2 3 4 5 6 7 8 9
              ↑ ↑
              l r
             (m)

8 = 8 所以結束二分搜

參考解答

d732
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;

void solve(int *data, int n, int qq) {
    int left = 0;
    int right = n;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (data[mid] < qq) {
            left = mid + 1;
        } else if (data[mid] > qq) {
            right = mid - 1;
        } else {
            cout << mid + 1 << "\n";
            return;
        }
    }
    cout << 0 << "\n";
    return;
}

int main() {
    int n, k;
    cin >> n >> k;
    int data[n], q[k];
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }
    for (int i = 0; i < k; i++) {
        cin >> q[i];
    }
    for (int i = 0; i < k; i++) {
        solve(data, n, q[i]);
    }
    return 0;
}