diff options
Diffstat (limited to 'PlaygroundCpp/Sources')
| -rw-r--r-- | PlaygroundCpp/Sources/Playground.cpp | 134 |
1 files changed, 74 insertions, 60 deletions
diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp index 6b9efff..39d31da 100644 --- a/PlaygroundCpp/Sources/Playground.cpp +++ b/PlaygroundCpp/Sources/Playground.cpp @@ -1,87 +1,101 @@ -#include <algorithm> -#include <sstream> #include <iostream> +#include <cassert> #include <vector> -#include <string> //#include <gtest/gtest.h> using std::vector; -using std::string; -bool compare_leading_digits(string s1, string s2) { - return stoi(s1 + s2) > stoi(s2 + s1); -} - -static string largest_number(vector<string> a) { - string result = ""; - string maxDigit = "0"; - int indexHolder = 0; - while (a.size() > 0){ - for (int i = 0; i< a.size(); i++) { - if (compare_leading_digits(a[i], maxDigit)) { - maxDigit = a[i]; - indexHolder = i; - } - } - result = result + maxDigit; - maxDigit = "0"; - a.erase(a.begin()+indexHolder); +int binary_search_recursive(const vector<long> &a, int low, int high, int key) { + if (high < low) { + return -1; } - return result; + 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); } -//TEST(CompareLeadingDigits, CompareTest1) { -// ASSERT_TRUE(compare_leading_digits("2", "21")); -//} -// -//TEST(CompareLeadingDigits, CompareTest2) { -// ASSERT_FALSE(compare_leading_digits("20", "21")); -//} -// -//TEST(CompareLeadingDigits, CompareTest3) { -// ASSERT_FALSE(compare_leading_digits("321", "322")); +//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; //} -// -//TEST(CompareLeadingDigits, CompareTest4) { -// ASSERT_FALSE(compare_leading_digits("321", "32")); + +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(CompareLeadingDigits, CompareTest5) { -// ASSERT_FALSE(compare_leading_digits("10", "1")); + +//test(binarysearch, search1) { +// vector<long> a { 1, 5, 8, 12, 13 }; +// assert_eq(binary_search(a, 8), 2); //} // -//TEST(CompareLeadingDigits, CompareTest6) { -// ASSERT_TRUE(compare_leading_digits("6", "10")); +//test(binarysearch, search2) { +// vector<long> a { 1, 5, 8, 12, 13 }; +// assert_eq(binary_search(a, 1), 0); //} // -//TEST(CompareLeadingDigits, CompareTest7) { -// ASSERT_TRUE(compare_leading_digits("23", "2")); +//test(binarysearch, search3) { +// vector<long> a { 1, 5, 8, 12, 13 }; +// assert_eq(binary_search(a, 23), -1); //} // -//TEST(CompareLeadingDigits, CompareTest8) { -// ASSERT_TRUE(compare_leading_digits("545", "54")); +//test(binarysearch, search4) { +// vector<long> a { 1, 5, 8, 12, 13 }; +// assert_eq(binary_search(a, 11), -1); //} // -//TEST(CompareLeadingDigits, CompareTest9) { -// ASSERT_TRUE(compare_leading_digits("56", "565")); +//test(binarysearch, search5) { +// vector<long> a { 3, 5, 8, 12, 13 }; +// assert_eq(binary_search(a, 2), -1); //} // -//TEST(LargestNumber, LargestTest1) { -// vector<string> nums = {"9", "4", "6", "1", "9"}; -// ASSERT_EQ("99641", largest_number(nums)); +//test(binarysearch, search6) { +// vector<long> a { 1, 5, 8, 12, 13 }; +// assert_eq(binary_search(a, 13), 4); //} // -//TEST(LargestNumber, LargestTest2) { -// vector<string> nums = {"21", "2"}; -// ASSERT_EQ("221", largest_number(nums)); +//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<string> a(n); - for (size_t i = 0; i < a.size(); i++) { - std::cin >> a[i]; - } - std::cout << largest_number(a); + 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]) << ' '; + } } |