alan23273850 的刷題筆記
d732: 二分搜尋法
Tags: binary-search
出處：https://zerojudge.tw/ShowProblem?problemid=d732
提交：https://zerojudge.tw/Submissions?problemid=d732&account=allllllan123456
問題：給定一個包含 $n\in[1,100000]$ 個 int 範圍的整數嚴格遞增序列，以及 $k\in[1,100000]$ 個 int 範圍的欲詢問整數，想知道這些整數分別在序列裡面的 index (令最前面元素的 index 為 1)，如果不存在則輸出 0。
解法：如標題，就二分搜，不解釋。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int arr[100001], n, k; cin >> n >> k;
6 for (int i=1; i<=n; i++) cin >> arr[i];
7 while (k--) {
8 int t; cin >> t;
9 int m, lb = 1, ub = n;
10 while (lb <= ub) {
11 m = (lb + ub) / 2;
12 if (arr[m] < t) lb = m + 1;
13 else if (t < arr[m]) ub = m - 1;
14 else break;
15 }
16 cout << (t==arr[m] ? m : 0) << '\n';
17 }
18 return 0;
19}