RecursionError：与进行二分搜索相比，超出了最大递归深度

Question

这是使用python的字典程序。但我发现了这样的错误。我想知道我看到的原因..如果你知道，请问我。

这是我得到的错误：

$ read datafile.txt

$ size

176050

$ find Yesterday

Traceback (most recent call last):

  File "C:/Users/LG/PycharmProjects/alg1/lesson1.py", line 55, in <module>

    word_index = binarysearch(words,word,0,len(words)-1)

  File "C:/Users/LG/PycharmProjects/alg1/lesson1.py", line 25, in binarysearch

    return binarysearch(data, target,middle+1, end)

  File "C:/Users/LG/PycharmProjects/alg1/lesson1.py", line 23, in binarysearch

    return binarysearch(data,target,begin,middle-1)

  File "C:/Users/LG/PycharmProjects/alg1/lesson1.py", line 23, in binarysearch

    return binarysearch(data,target,begin,middle-1)

  File "C:/Users/LG/PycharmProjects/alg1/lesson1.py", line 23, in binarysearch

    return binarysearch(data,target,begin,middle-1)

  [Previous line repeated 994 more times]

  File "C:/Users/LG/PycharmProjects/alg1/lesson1.py", line 13, in binarysearch

    if begin > end:

RecursionError: maximum recursion depth exceeded in comparison

Process finished with exit code 1

这是我的代码：

def datafile(file):

    f = open(file,'rt',encoding='UTF8')

    while True:

        line = f.readline()

        if not line:

            break

        if line == '\n':

            continue

        lines.append(line.split('\n')[0])

    return lines

def binarysearch(data,target,begin,end):

    if begin > end:

        if data[end]:  #"end" index's front data exist  

            return end

        else:

            return -1

    else:

        middle = int(begin+end/2)

        if data[middle] == target:

            return middle

        elif data[middle] > target:

            return binarysearch(data,target,begin,middle-1)

        else:

            return binarysearch(data, target,middle+1, end)

if __name__=="__main__":

    lines = []  # all list

    words = []  # list that all words is changed to lower

    pos = []  # word's pos list

Answer 1

你的二分搜索算法有错误：middle&nbsp;=&nbsp;int(begin+end/2)由于除法优先于加法，因此不会计算中间位置。它可能导致middle变得大于end，如果data[middle] > target那么下一个间隔将在下一次递归调用中更大。这会导致无限递归。更正为：middle&nbsp;=&nbsp;int((begin+end)/2)或者干脆：middle&nbsp;=&nbsp;(begin+end)//2