Python 平分列表

Question

我需要编写一个函数，它接受一个列表并将其平分（就像 bisect 模块一样，但我不能使用它）。我通常会展示到目前为止我所做的事情，但我真的不知道如何在没有模块的情况下做到这一点，所以我希望有人可以帮助我一点。这是我需要弄清楚的确切问题：

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

Answer 1

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

所以我稍微调整了一下：

这是我的版本：

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

希望这可以帮助那些苦苦挣扎的人使用二等分程序

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) 

如果大师可以帮助我纠正这个缺陷，那就太好了，谢谢，

Answer 2

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)

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