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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#include <iostream>
#include <cassert>
#include <vector>
//#include <gtest/gtest.h>
using std::vector;
int binary_search_recursive(const vector<long> &a, int low, int high, int key) {
if (high < low) {
return -1;
}
int mid = (low + (high - low) / 2);
if (key == a[mid]) {
return mid;
} else if (key < a[mid]) {
return binary_search_recursive(a, low, mid - 1, key);
} else
return binary_search_recursive(a, mid + 1, high, key);
}
//int binary_search_iterative(const vector<long> &a, int low, int high, int key) {
// while (low <= high) {
// int mid = (low + (high - low) / 2);
// if (key == a[mid]) {
// return mid;
// } else if (key < a[mid]) {
// high = mid - 1;
// } else {
// low = mid + 1;
// }
// }
// return -1;
//}
int binary_search(const vector<long> &a, int x) {
int left = 0, right = (int) a.size();
return binary_search_recursive(a, left, right, x);
}
//int linear_search(const vector<int> &a, int x) {
// for (size_t i = 0; i < a.size(); ++i) {
// if (a[i] == x)
// return i;
// }
// return -1;
//}
//test(binarysearch, search1) {
// vector<long> a { 1, 5, 8, 12, 13 };
// assert_eq(binary_search(a, 8), 2);
//}
//
//test(binarysearch, search2) {
// vector<long> a { 1, 5, 8, 12, 13 };
// assert_eq(binary_search(a, 1), 0);
//}
//
//test(binarysearch, search3) {
// vector<long> a { 1, 5, 8, 12, 13 };
// assert_eq(binary_search(a, 23), -1);
//}
//
//test(binarysearch, search4) {
// vector<long> a { 1, 5, 8, 12, 13 };
// assert_eq(binary_search(a, 11), -1);
//}
//
//test(binarysearch, search5) {
// vector<long> a { 3, 5, 8, 12, 13 };
// assert_eq(binary_search(a, 2), -1);
//}
//
//test(binarysearch, search6) {
// vector<long> a { 1, 5, 8, 12, 13 };
// assert_eq(binary_search(a, 13), 4);
//}
//
//test(binarysearch, search7) {
// vector<long> a { 1, 5, 8, 12, 13 };
// assert_eq(binary_search(a, 12), 3);
//}
int main() {
int n;
std::cin >> n;
vector<long> a(n);
for (size_t i = 0; i < a.size(); i++) {
std::cin >> a[i];
}
int m;
std::cin >> m;
vector<long> b(m);
for (int i = 0; i < m; ++i) {
std::cin >> b[i];
}
for (int i = 0; i < m; ++i) {
//replace with the call to binary_search when implemented
std::cout << binary_search(a, b[i]) << ' ';
}
}
|
