From 952c14b4bad84fceb4a3ba812137729f35e936f1 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Wed, 10 Oct 2018 21:26:45 -0500 Subject: Binary search done! It was interesting that int in jave has a bigger range than int in C++ Java: https://cs.fit.edu/~ryan/java/language/java-data.html C++: https://stackoverflow.com/questions/1819189/what-range-of-values-can-integer-types-store-in-c I used vector initially, which failed on grader's test case 17/36. Changing that to vector fixed it! Also interesting that recursive approach appears to be slightly faster with slighter bigger memory usage.--- PlaygroundCpp/Sources/Playground.cpp | 134 +++++++++++++++++++---------------- 1 file changed, 74 insertions(+), 60 deletions(-) (limited to 'PlaygroundCpp') 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 -#include #include +#include #include -#include //#include 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 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 &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 &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 &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(CompareLeadingDigits, CompareTest5) { -// ASSERT_FALSE(compare_leading_digits("10", "1")); + +//test(binarysearch, search1) { +// vector 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 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 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 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 a { 3, 5, 8, 12, 13 }; +// assert_eq(binary_search(a, 2), -1); //} // -//TEST(LargestNumber, LargestTest1) { -// vector nums = {"9", "4", "6", "1", "9"}; -// ASSERT_EQ("99641", largest_number(nums)); +//test(binarysearch, search6) { +// vector a { 1, 5, 8, 12, 13 }; +// assert_eq(binary_search(a, 13), 4); //} // -//TEST(LargestNumber, LargestTest2) { -// vector nums = {"21", "2"}; -// ASSERT_EQ("221", largest_number(nums)); +//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]; - } - std::cout << largest_number(a); + 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]) << ' '; + } } -- cgit v1.2.3