在列表中确定位置的正确实施

Question

我有一个喜欢的电影列表，我想根据我的口味从最好的电影（有最多的点数）到最差的电影（只有1点）进行排序。

比方说，该列表包含已排序的300部电影，并且您想确定新电影的分数。您可以将新电影与排序列表中的每部电影进行比较，也可以利用列表排序的知识。

我试图将它作为二进制搜索来实现，因此每个插入（新电影）都具有对数复杂性。 二进制搜索实现很容易对我来说：

def binSearch(lst, number): 
    left = 0 
    right = len(lst) - 1 
    while left <= right: 
    middle = left + ((right - left)/2) 
    if number == lst[middle]: 
     return True 
    else: 
     if number < lst[middle]: 
     right = middle - 1 
     else: 
     left = middle + 1 
    return False 

但要确定点是相当困难的我。我已经调试了几个小时，但仍然出现了一些错误。我多次改变了实现，但没有任何帮助。 这是我最后的解决方案（也许该算法是在最坏的状态，那么它是在开头）

def determinePoints(lst, new): 
    # lst is a list of tuples with movies 
    # new is a tuple with new movie (has no point associated yet) 
    if not lst: # no movie has points so far 
    return 1 # now exists only one movie with associated points 
    newTitle = new[0] 
    newGenre = new[1] 
    atMost = len(lst) 
    atLeast = 0 
    while atLeast < atMost - 1: # algorithm doesn't work 
           # if only two movies have associated points 
    center = twoPointsCenter(atLeast, atMost) 
    (title, genre) = lst[center] 
    os.system("clear") 
    competitionStrings = [ newTitle, newGenre, "\n" * 10, title, genre ] 
    print "\n".join([ x.center(150) for x in competitionStrings ]) 
    c = getch() 
    if c == "j": # new movie is worse than this 
     atMost = center - 1 
     if atMost <= 1: 
     return 1 
    else: # new movie is better than this 
     atLeast = center + 1 
     if atLeast >= len(lst): 
     return max(atLeast, 1) 
    return max(twoPointsCenter(atLeast, atMost), 1) 

def twoPointsCenter(left, right): 
    return left + ((right - left)/2) 

你能纠正我的解决方案（或更好的实现它）转变和正确的结果结束？

它应该从0,1,2，等等的长度开始工作。它不应该返回小于1的值。在电影列表中不应该有两个具有相同数量的电影点。

当函数determinePoints返回点时，我将更新此影片的数据库，并且每个影片的点数大于此新影片的增量点数1。

谢谢

Answer 1

我认为你需要更好看的边界指标。 len(lst)比最大索引大一个，例如：列表是基于0的。我冒昧地使用0作为最低分数;这将直接给你的位置lst.insert在。另外，我无法抗拒，并且让这个更像PEP 8。

你不需要所有的角落案例;我认为他们工作得很好。

def determine_points(lst, new): 
    # lst is a list of tuples with movies, ranked by how good the movie is 
    # new is a tuple with new movie 
    # the new movies position is to be determined 

    new_title, new_genre = new 
    at_most = len(lst) 
    at_least = 0 
    while at_least < at_most: 
    center = (at_least + at_most) // 2 
    title, genre = lst[center] 
    os.system("clear") 
    competition_strings = [new_title, new_genre, "\n" * 10, title, genre] 
    print("\n".join(x.center(150) for x in competition_strings)) 
    c = getch() 
    if c == "j": # new movie is worse than this 
     at_most = center 
    else: # new movie is better than this 
     at_least = center + 1 
    return at_least 

编辑：我用下面的代码进行测试。

lst = [] 
news = [(str(i), str(i)) for i in range(10)] 
import random 
random.shuffle(news) 
for new in news: 
    print(lst) 
    lst.insert(determine_points(lst, new), new) 
print(lst)