二分查找功能，测试失败，因为比较计数器不起作用

Question

FAIL: test_small_all_common_comparisons (__main__.SmallTestsBinary)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/pg/Downloads/2023s2_cosc122_assignment1 (3)/student_files/tests.py", line 221, in test_small_all_common_comparisons
    self.comparisons_test(test_file)
  File "/Users/pg/Downloads/2023s2_cosc122_assignment1 (3)/student_files/tests.py", line 163, in comparisons_test
    super().comparisons_test(test_file_name,
  File "/Users/pg/Downloads/2023s2_cosc122_assignment1 (3)/student_files/tests.py", line 115, in comparisons_test
    self.assertIn(student_count, valid_count_range, message_if_wrong)
AssertionError: 10 not found in range(38, 53) : Your code reported using 10 Gene comparisons but it should use 38 <= comparisons < 53.


from classes import GeneList


def binary_search(arr, target):
    """Helper function for binary search."""
    left, right = 0, len(arr) - 1
    while left <= right:
        middle = (left + right) // 2
        if arr[middle] == target:
            return True, middle  # Gene found, return True and index
        elif arr[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
    return False, None  # Gene not found, return False and None

def binary_gene_match(first_genome, second_genome):
    comparisons = 0
    common_genes = GeneList()

    for gene in first_genome:
        # Perform binary search using the helper function
        found, _ = binary_search(second_genome, gene)
        

        if found:
            common_genes.append(gene)
            comparisons += 1  # Increment comparison count for each gene
    return common_genes, comparisons

Answer 1

我认为@MarkRansom 是对的。 并且计算比较应该以不同的方式进行。计算搜索过程中进行的比较怎么样？ 像这样。

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    comparison = 0
    while left <= right:
        middle = (left + right) // 2
        comparison += 1
        if arr[middle] == target:
            return True, comparison # Gene found, return True and comparison counts
        elif arr[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
    return False, comparison # Gene not found, return False and the comparison  counts

def binary_gene_match(first_genome, second_genome):
    comparisons = 0
    common_genes = GeneList()

    for gene in first_genome:
        # Perform binary search using the helper function
        found, comparison = binary_search(second_genome, gene)
        

        if found:
            common_genes.append(gene)
            comparisons += comparison  # Increment comparison count for each gene
    return common_genes, comparisons

或者即使你没有找到该基因，你也应该计算比较。