forked from indy256/codelibrary
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary_search.cpp
More file actions
48 lines (43 loc) · 1.3 KB
/
binary_search.cpp
File metadata and controls
48 lines (43 loc) · 1.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
int binary_search(bool (*f)(int) /* function<bool(int)> f */, int from_inclusive, int to_inclusive) {
// invariant: f[lo] == false, f[hi] == true
int lo = from_inclusive - 1;
int hi = to_inclusive + 1;
// while there are some elements between lo and hi
while (hi - lo > 1) {
// invariant: lo < mid < hi
int mid = (lo + hi) / 2;
if (!f(mid)) {
lo = mid;
} else {
hi = mid;
}
}
// here lo + 1 == high
return hi;
}
// binary_search(new bool[5]{false, false, false, true, true}, 0, 4) == 3
int binary_search(bool a[], int from_inclusive, int to_inclusive) {
// invariant: f[lo] == false, f[hi] == true
int lo = from_inclusive - 1;
int hi = to_inclusive + 1;
// while there are some elements between lo and hi
while (hi - lo > 1) {
// invariant: lo < mid < hi
int mid = (lo + hi) / 2;
if (!a[mid]) {
lo = mid;
} else {
hi = mid;
}
}
// here lo + 1 == high
return hi;
}
// usage example
int main() {
int first_true = binary_search([](int x) { return x >= 4; }, 0, 10);
cout << (first_true == 4) << endl;
cout << (binary_search(new bool[3]{false, true, true}, 0, 2) == 1) << endl;
}