回答編集履歴
1
追加説明
test
CHANGED
|
@@ -7,3 +7,29 @@
|
|
|
7
7
|
std::binary_search の comp は
|
|
8
8
|
|
|
9
9
|
comp(const T& a, const T& b) { return a < b; } だから、速いのではありませんか？
|
|
10
|
+
|
|
11
|
+
|
|
12
|
+
|
|
13
|
+
|
|
14
|
+
|
|
15
|
+
もうひとつ。
|
|
16
|
+
|
|
17
|
+
|
|
18
|
+
|
|
19
|
+
バイナリサーチでは、結果が求まるまで何回か比較を行います。
|
|
20
|
+
|
|
21
|
+
comp_result == 0 は最後まで true にならないので、
|
|
22
|
+
|
|
23
|
+
comp_result == 0 と comp_result < 0 の 2回の比較が常に行われます。
|
|
24
|
+
|
|
25
|
+
|
|
26
|
+
|
|
27
|
+
std::binary_search では comp が less なので、
|
|
28
|
+
|
|
29
|
+
if (key < *mid) end = mid;
|
|
30
|
+
|
|
31
|
+
else if (*mid < key) it = mid, ++it;
|
|
32
|
+
|
|
33
|
+
else return mid;
|
|
34
|
+
|
|
35
|
+
になっていて、比較が 1回で済む場合があるのではないでしょうか？
|