From 5558c3b43f4e6c8501c218b8871cb353cbd9344f Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Fri, 16 Nov 2018 20:50:55 -0600
Subject: Majority Element finally done!

Wow, it took awhile to finish. Work has been busy and I haven't had time
to hack...---
 PlaygroundCpp/Sources/Playground.cpp | 112 +++++++++--------------------------
 1 file changed, 28 insertions(+), 84 deletions(-)

diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp
index 39d31da..e9f516d 100644
--- a/PlaygroundCpp/Sources/Playground.cpp
+++ b/PlaygroundCpp/Sources/Playground.cpp
@@ -1,101 +1,45 @@
-#include <iostream>
-#include <cassert>
 #include <vector>
+#include <iostream>
 //#include <gtest/gtest.h>
 
 using std::vector;
 
-int binary_search_recursive(const vector<long> &a, int low, int high, int key) {
-	if (high < low) {
-		return -1;
+int conquer(vector<int> &a, int b, int c, int left, int right) {
+	int countB = 0;
+	int countC = 0;
+	for (int i = left; i < right + 1; i++) {
+		if (a[i] == b)
+			countB++;
+		if (a[i] == c)
+			countC++;
 	}
-	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);
+	if (countB > (right - left + 1) / 2)
+		return b;
+	if (countC > (right - left + 1) / 2)
+		return c;
+	return -1;
 }
 
-//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;
-//}
-
-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 get_majority_element(vector<int> &a, int left, int right) {
+	if (left == right)
+		return a[left];
+	int middle = (right - left) / 2;
+	int b = get_majority_element(a, left, left + middle);
+	int c = get_majority_element(a, left + middle + 1, right);
+	int d = conquer(a, b, c, left, right);
+	return d;
 }
-
-//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(binarysearch, search1) {
-//	vector<long> a { 1, 5, 8, 12, 13 };
-//	assert_eq(binary_search(a, 8), 2);
-//}
-//
-//test(binarysearch, search2) {
-//	vector<long> a { 1, 5, 8, 12, 13 };
-//	assert_eq(binary_search(a, 1), 0);
-//}
-//
-//test(binarysearch, search3) {
-//	vector<long> a { 1, 5, 8, 12, 13 };
-//	assert_eq(binary_search(a, 23), -1);
-//}
-//
-//test(binarysearch, search4) {
-//	vector<long> a { 1, 5, 8, 12, 13 };
-//	assert_eq(binary_search(a, 11), -1);
-//}
-//
-//test(binarysearch, search5) {
-//	vector<long> a { 3, 5, 8, 12, 13 };
-//	assert_eq(binary_search(a, 2), -1);
-//}
-//
-//test(binarysearch, search6) {
-//	vector<long> a { 1, 5, 8, 12, 13 };
-//	assert_eq(binary_search(a, 13), 4);
-//}
-//
-//test(binarysearch, search7) {
-//	vector<long> a { 1, 5, 8, 12, 13 };
-//	assert_eq(binary_search(a, 12), 3);
+//TEST(MajorityElement, test1) {
+//	vector<int> a = { 1, 1 };
+//	ASSERT_EQ(get_majority_element(a, 0, a.size()-1), 1);
 //}
 
 int main() {
 	int n;
 	std::cin >> n;
-	vector<long> a(n);
-	for (size_t i = 0; i < a.size(); i++) {
+	vector<int> 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]) << ' ';
-	}
+	std::cout << (get_majority_element(a, 0, n - 1) != -1) << '\n';
 }
-- 
cgit v1.2.3