Python 列表二分查找

Question

我需要写一个函数，这个函数要把一个列表一分为二（就像 bisect 模块那样，但我不能使用那个模块）。我通常会展示我到目前为止做了什么，但我真的不知道没有这个模块该怎么做，所以我希望有人能帮我一点。这里是我需要弄清楚的具体问题：

写一个叫做 bisect 的函数，这个函数接收一个已经排好序的列表和一个目标值，如果这个值在列表里，就返回它的索引；如果不在，就返回 None。

Answer 1

我在做《Think Python》第10章第8题的作业，试了试Fred写的代码，但发现有一些问题。

1. 这个计数器在处理有10万个字符串的长列表时不太好使。

2. 有时候它会返回None，但我确定这些东西在列表里。

所以我稍微改了一下：

这是我的版本：

它运行得很好，我用一个名为words.txt的单词列表进行了测试，这个列表来自Swampy 2.0，原本是Moby Collection中的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) 

如果有高手能帮我修正这个缺陷，那就太好了，谢谢！

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)

这基本上就是在做二分查找。索引被传递用来跟踪原始列表中的位置，这样在递归调用的后续过程中就能知道每个元素的位置。