二分探索でTLEになる理由が分かりません。

Question

AOJの問題、ALDS1_4_Bに対して、以下のコードを書きましたが、テストケース10でTLE（Time Limit Exceeded）になってしまします。計算量はO(qlogn)で収まっていると思うのですが、なぜTLEになってしまうのでしょうか？

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

bool binarySearchJudge(vector<int> a, int index, int key)
{
	if (key <= a[index]) return true;
	else return false;
}

int binarySearch(vector<int> a, int key)
{
	int ng = -1;
	int ok = a.size();
	while (1 < abs(ng - ok))
	{
		int mid = (ng + ok) / 2;
		if (binarySearchJudge(a, mid, key)) ok = mid;
		else ng = mid;
	}
	return a[ok] == key;
}

int main()
{
	int n;
	cin >> n;
	vector<int> s(n);
	for (int i = 0; i < n; i++)
	{
		cin>>s[i];
	}
	
	int q;
	cin >> q;
	int ans = 0;
	for (int i = 0; i < q; i++)
	{
		int t;
		cin>>t;
		if (binarySearch(s, t)) ans++;
	}
	cout << ans << endl;
}

Answer 1

binarySearchJudge と binarySearch の引数に vector がありますが、この渡し方だと関数を呼ぶたびに vector がコピーされます。コピーに係る処理時間を O(n) だとして、q回ループするので O(n*q) ほどの時間がかかっちゃって TLE になってるんだろうと思います。

次のように参照渡しにするとコピーが行われず、間に合うはずなので試してみてください。

- bool binarySearchJudge(vector<int> a, int index, int key)
+ bool binarySearchJudge(const vector<int> &a, int index, int key)

- int binarySearch(vector<int> a, int key)
+ int binarySearch(const vector<int> &a, int key)

Comments

[sumachu]

ご回答ありがとうございます。無事ACしました。値渡しですので、vectorを呼び出す度にコピーされてますね。確かにconst参照なら、呼び出す度にコピーされないですね。クラスを引数にする時はコンストラクタを呼び出さないために、const参照しているのですが、よく考えたら、vectorの場合も同じく、const参照にしておいたほうがよさそうですね。

Answer 2

見たところオーダー上は問題がなさそうなので単純に最大50000個の対象を1秒以内に処理し切れていないのかと。

とりあえず、ただの比較を関数にしたり途中で探索対象が見つかっても最後まで探索してたり無駄があります。

あと余計かも知れませんが変数名ok,ngは何がOKなのか意味不明なので正しい名前にしましょう。

Comments

[sumachu]

ご回答ありがとうございます。
>>ただの比較を関数にしていたり...
結果的にvectorの関数の渡し方に問題がありました。関数を呼び出す度にvectorがコピーされるのがTLEの原因でした。

>>途中で探索対象が見つかっても最後まで探索したり...
ご指摘の通りです。ただ、これには少し理由がありまして、二分探索に汎用性を持たせるために、lower_boundとupper_boundの実装も兼ねています。そのため、最後まで探索しています。こちらのURLを参考に実装しています。https://qiita.com/drken/items/97e37dd6143e33a64c8c

[退会済みユーザー]

リンク先見ましたがok,ngの初期値が関数内で設定されてる時点で常にok>ngなのでupperは兼ねてないと思いますが...

これは個人的な感想ですが上記のok,ngの書記長の話を除けば確かに記述を共通化できてはいますが可読性をドブに捨てるなぁと。
バグが少ないって書いてるけど、一度確立した物をコピペする分にはバグがない(どんな実装でも当然)ってだけでこれを0から実装した場合無駄にトリッキーでバグの発生源にしか見えないです･･･

[sumachu]

すみません。確かにコードを少しいじらない限り、upper_boundは兼ねていませんね。ご指摘の通り、実際に0から上記コードを実装しましたが、何度もデバッグして修正しました。通常の二分探索の実装に比べて、とてもややこしかったです。（現在は競技プログラミングに取り組み中ですので、一度はこの手のアルゴリズムを自分の手で実装してみることにしています。）