a guest Aug 24th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
- """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
- while first < last and not fraud:
- total_comparisons += 2
- if Voter < first_booth_voters[index]:
- last = index - 1
- first = index + 1
- if Voter == first_booth_voters[index]:
- fraud = True
- return results, comparisons
RAW Paste Data