典型アルゴリズム問題集 A問題（二分探索）を解く

AtCoder で公開されている「典型アルゴリズム問題集」のA問題をC++で解いてみました。

A問題 二分探索

問題はリンク先をご覧ください。

A 二分探索の練習問題

二分探索で解いてみます。

解答案

C++ プログラム例

数列 $A_i$ は、小さい順番からソートされています。このため、lower_bound で $A_i \geqq K$ となる最小のインデックス $i$ を求めることができます。

なお、このプログラムは長さ $N$ の数列を読み込んでいます。このため、計算量は、$O(N)$ となります。線形探索でも計算量は変わりませんが、問題の趣旨を考慮して二分探索で解きました。

以下が、C＋＋プログラムとなります。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	auto it = lower_bound(a.begin(), a.end(), k);
	if (it != a.end()) {
		cout << it - a.begin() << endl;
	} else {
		cout << -1 << endl;
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

最後に

この問題集は、『マイナビ出版「アルゴリズム実技検定 公式テキスト[エントリー~中級編]」に掲載されている練習問題のジャッジを提供することを目的としています』と記載されていました。

わたくしには、ちょうど良い難易度ですべてを解くことができたため、解答案を紹介していきます。