#include #include #include //#include using std::vector; int binary_search_recursive(const vector &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 &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 &a, int x) { int left = 0, right = (int) a.size(); return binary_search_recursive(a, left, right, x); } //int linear_search(const vector &a, int x) { // for (size_t i = 0; i < a.size(); ++i) { // if (a[i] == x) // return i; // } // return -1; //} //test(binarysearch, search1) { // vector a { 1, 5, 8, 12, 13 }; // assert_eq(binary_search(a, 8), 2); //} // //test(binarysearch, search2) { // vector a { 1, 5, 8, 12, 13 }; // assert_eq(binary_search(a, 1), 0); //} // //test(binarysearch, search3) { // vector a { 1, 5, 8, 12, 13 }; // assert_eq(binary_search(a, 23), -1); //} // //test(binarysearch, search4) { // vector a { 1, 5, 8, 12, 13 }; // assert_eq(binary_search(a, 11), -1); //} // //test(binarysearch, search5) { // vector a { 3, 5, 8, 12, 13 }; // assert_eq(binary_search(a, 2), -1); //} // //test(binarysearch, search6) { // vector a { 1, 5, 8, 12, 13 }; // assert_eq(binary_search(a, 13), 4); //} // //test(binarysearch, search7) { // vector a { 1, 5, 8, 12, 13 }; // assert_eq(binary_search(a, 12), 3); //} int main() { int n; std::cin >> n; vector a(n); for (size_t i = 0; i < a.size(); i++) { std::cin >> a[i]; } int m; std::cin >> m; vector 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]) << ' '; } }