为什么我的二分查找使用了这么多比较？

Question

这是我的代码：

def binary_search(sortedlist,target,comparisons):
start = 0
end = len(sortedlist) - 1


while(end - start >= 0):
    mid = (start + end)//2
    comparisons += 2
    if(target < sortedlist[mid]):
        comparisons -= 1
        end = mid - 1
    elif(target > sortedlist[mid]):
        start = mid + 1
    else:
        return target, comparisons
return False, comparisons

它与此处关于二进制搜索的所有其他 post 基本相同，但出于某种原因，它使用了太多比较。

这是我自己修改后的代码

from classes import GeneList
## Uncomment the following line to be able to make your own testing Genes
# from classes import Gene, Genome

def binary_search(sortedlist, target, comparisons):
    reducedlist = sortedlist

    while len(reducedlist) > 1:
        mid = len(reducedlist) // 2
        comparisons += 1
        if target < reducedlist[mid]:
            reducedlist = reducedlist[:mid]
        else:
            reducedlist = reducedlist[mid:]

    comparisons += 1
    if reducedlist[0] == target:
        return reducedlist[0], comparisons
    else:
        return False, comparisons


def genetic_similarity_binary(first_genome, second_genome):
    """ This function takes two Genome objects, and returns a GeneList
    and an integer. The GeneList is of all genes that are common
    between first_genome and second_genome, while the integer is
    how many comparisons it took to find all the similar genes.
    Hint: it might pay to define a helper function.
    """
    comparisons = 0
    similar_list = GeneList()
    for target in first_genome:
        result, comparisons = binary_search(second_genome, target, comparisons)
        if result:
            similar_list.append(result)
    return similar_list, comparisons

您不必进行中间检查

Answer 1

出于优化目的，您应该首先检查终止条件。试试这个方法，

def binary_search(sortedlist,target,comparisons):
start = 0
end = len(sortedlist) - 1


while(end - start >= 0):
    mid = (start + end)//2
    comparisons += 2
    if(target == sortedlist[mid]):
        comparisons -= 1
        return target, comparisons
    elif(target > sortedlist[mid]):
        start = mid + 1
    else:
        end = mid - 1
return False, comparisons

与执行 binary_search([1,2,3,4,5,6,7,8,9,10],9,0)

时一样

您的代码给出的结果为 (9, 6) ，上述更改将其给出为 (9, 5)

Answer 2

你应该先在你的程序中搜索第三个条件，然后做那个需要的...因为第三个条件实际上是应该首先给出的终止条件...试试看。

Answer 3

我自己解决了这个问题，使用的比较要少得多，而不是每次都检查它是否相等。在作业结束之前，我无法 post 我的代码。

为什么我的二分查找使用了这么多比较？

Why does my binary search use so many comparisons?

search

binary-search

python-3.x