summaryrefslogtreecommitdiff
path: root/PlaygroundCpp
diff options
context:
space:
mode:
authorHaidong Ji2018-10-10 21:26:45 -0500
committerHaidong Ji2018-10-10 21:26:45 -0500
commit952c14b4bad84fceb4a3ba812137729f35e936f1 (patch)
tree5ff17dd43279fbfd9584edb3feb60dbfcff849fa /PlaygroundCpp
parentfc245a6f71f57f5131d46c62cd42929968689e4b (diff)
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<int> initially, which failed on grader's test case 17/36. Changing that to vector<long> fixed it! Also interesting that recursive approach appears to be slightly faster with slighter bigger memory usage.
Diffstat (limited to 'PlaygroundCpp')
-rw-r--r--PlaygroundCpp/Sources/Playground.cpp134
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]) << ' ';
+ }
}