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

題目連結

題目大意

給定一個嚴格遞增的數列和 $q$ 筆詢問，每次詢問一個數字是否在數列中出現？

題解

由於數列已經排序過了，因此我們可以直接用二分搜找 $x$ 是否在數列中出現。二分搜的概念與小時候玩的猜數字一樣，每次猜中間的數字，如果比答案小，往更大的那一半在猜，否則往更小的那一半猜，持續直到找到答案。如果使用 C++ 的話有內建的 std::lower_bound 可以做使用，函式會回傳第一個 $\geq x$ 元素的 iterator，我們只需要檢查該 iterator 是否為 end 或是 iterator 的數值是否 $= x$ 即可。其他實作的細節請參考 code。

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	while(q--) {
		int x;
		cin >> x;
		auto it = lower_bound(a.begin(), a.end(), x);
		if(it != a.end() && *it == x) {
			cout << it - a.begin() + 1 << "\n";
		} else {
			cout << "0\n";
		}
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge d732 - 二分搜尋法