"""Module for detecting voter fraud using binary search."""
from classes import VoterList
from tools import make_voter_list


def fraud_detect_binary(first_booth_voters, second_booth_voters):
    """This function takes VoterLists from two voting booths as input.
    You can assume that the second VoterList is in lexicogrpahic order, that is,
    the second list is already sorted alphabetically.

    The function returns a VoterList and an integer.
    The VoterList contains the voters who cast a vote in both booths (ie, frauds),
    The integer is the number of VoterName comparisons the function made.
    """
    results = []
    total_comparisons = 0

    #supplementary video
    for Voter in first_booth_voters:
        first = 0
        last = len(second_booth_voters) - 1
        fraud = False
        index = (first + last) // 2

        if len(results) == len(first_booth_voters):
            total_comparisons += 1
            break
        else:
            while first < last and not fraud:
                total_comparisons += 2
                if Voter < first_booth_voters[index]:
                    last = index - 1
                else:
                    first = index + 1

            if Voter == first_booth_voters[index]:
                results.append(Voter)
                fraud = True

    return results, comparisons