Election interview question

election.cc

// You are given a sorted array of numbers where each number represents a
// candidate in an election. For example, in the list below candidate 1 received
// 2 votes, candidate 2 received 1 vote, candidate 3 received 6 votes, etc.
// [1, 1, 2, 3, 3, 3, 3, 3, 3, 4, 5]
// A candidate wins an election if and only if they have strictly greater than
// 50% of the votes.
// Write a function to determine the winning candidate, if any.

#include <optional>
#include <vector>

enum class SearchBound {
  kLower,
  kUpper,
};

template <class T>
auto BinarySearch(const std::vector<T>& list, const T& target,
                  const SearchBound bound) 
    -> std::optional<typename std::vector<T>::const_iterator> {
  if (list.empty()) return {};
  auto low = list.begin();
  auto high = list.end() - 1;
  while (low < high) {
    const auto middle =
        low + (high - low + static_cast<int>(bound == SearchBound::kUpper)) / 2;
    switch (bound) {
      case SearchBound::kLower:
        if (*middle < target) {
          low = middle + 1;
        } else {
          high = middle;
        }
        break;
      case SearchBound::kUpper:
        if (target < *middle) {
          high = middle - 1;
        } else {
          low = middle;
        }
        break;
    }
  }
  if (*low != target) return {};
  return low;
}

template <class T>
auto Election(const std::vector<T>& ballots) -> std::optional<T> {
  const auto begin = ballots.begin();
  const auto end = ballots.end();
  const auto candidate = begin + (end - begin) / 2;
  const auto lower = BinarySearch<T>(ballots, *candidate, SearchBound::kLower);
  const auto upper = BinarySearch<T>(ballots, *candidate, SearchBound::kUpper);
  if (!lower.has_value() || !upper.has_value()) return {};
  if (ballots.size() < 2 * (upper.value() - lower.value() + 1)) {
    return *candidate;
  }
  return {};
}