python - Python二等分列表

Question

我需要编写一个函数来获取一个列表并将其一分为二（如 bisect 模块，但我不能使用它）。我通常会展示我到目前为止所做的事情，但如果没有模块，我真的不知道该怎么做，所以我希望有人可以帮助我。这是我需要弄清楚的确切问题：

编写一个名为 bisect 的函数，它接受一个排序列表和一个目标值，如果存在则返回该值在列表中的索引，如果不存在则返回 None

Answer 1

bisect 模块跟踪列表，保持排序，而不必每次插入元素时都使用。您需要实现的方法只需要在排序列表中进行搜索。

def bisect(sortedlist,targetvalue,firstindex=0,lastindex=None):

    if(len(sortedlist)==0):
        return None
    if(len(sortedlist)==1):
        if(sortedlist[0]==targetvalue):
            return firstindex
        else:
            return None
    center = int(round(len(sortedlist)/2))

    if(sortedlist[center]==targetvalue):
        return firstindex+center
    if(targetvalue>sortedlist[center]):
        return bisect(sortedlist[center+1:lastindex],targetvalue,center+1,lastindex)
    else:
        return bisect(sortedlist[0:center],targetvalue,firstindex,center-1)

这基本上是进行二进制搜索。传递索引以跟踪原始列表的索引，在递归循环中进一步调用。

Answer 2

我正在做“think python”第 10 章练习 8 的作业，我厌倦了上面由 fred 编写的代码。它似乎有一些错误。1. 计数器不适用于包含 100k 字符串的长列表 2. 有时它会返回 None 对于我确定在列表中的东西。

所以我稍微调整了一下：

这是我的版本：

它工作得很好，它使用来自 swampy 2.0 的名为 words.txt 的单词表对其进行了测试，该单词表最初来自 moby 集合：113809of.fic

希望这可以帮助那些在 bisect 计划中苦苦挣扎的人

def bisects (list,x,counter=0):

    if len(list)==0:
        return x,'is not in the list'
    elif(len(list)==1):
        middle = 0
    else:
        middle = int(len(list)/2)

    if x == list[middle]:
        return counter, x,'is in the list' 
    elif x < list[middle]:
        counter +=0
        return bisects(list[0:middle],x,counter)
    elif x > list[middle]:
        counter +=middle
        return bisects(list[middle+1:],x,counter) 

如果大师可以帮助我纠正这个缺陷也将很棒，谢谢，