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<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.---
 PlaygroundCpp/Sources/Playground.cpp | 134 +++++++++++++++++++----------------
 1 file changed, 74 insertions(+), 60 deletions(-)

(limited to 'PlaygroundCpp/Sources')

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]) << ' ';
+	}
 }
-- 
cgit v1.2.3