在列表中確定位置的正確實施

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)