Python IndexError：查看if語句時列表索引超出範圍

Question

我無法克服此錯誤。我正在做一個類似mergesort合併的例程。也許我正在實例化錯誤。下面的代碼：

def MergeAndCountSplitInv(arr, length): 
    left = arr[0:length/2] 
    right = arr[length/2+1: length] 

    i = 0 
    j = 0 
    numSplitInv = 0 
    newArray = [0] * length 
    for k in range(len(arr)): 
     if (left[i] < right[j]): 
      #newArray.insert(k, left[i]) 
      newArray.append(left[i]) 
      i = i + 1 
     else: #(right[j] < left[i] 
      #newArray[k].insert(k, right[j]) 
      newArray.append(right[j]) 
      j = j + 1 
      numSplitInv = numSplitInv + (length/2 - i) 

    return ReturnValue(newArray, numSplitInv) 

誤差給出如下：

File "InversionCount.py", line 31, in MergeAndCountSplitInv if (left[i] < right[j]): IndexError: list index out of range

感謝您的幫助

Answer 1

的一個問題是你的片指標的理解。這兩條線路：

left = arr[0:length/2] 
right = arr[length/2+1: length] 

應改爲：

left = arr[:length/2] 
right = arr[length/2:] 

開始索引被包括在內，最終指數是包含在片中的第一件不，所以要得到一個完整的分區，您在左側的末尾使用與右側相同的索引。

但真正的問題是，你增加i和j沒有檢查您是否已經走了的left或right結束，所以你最終得到的索引錯誤。

Answer 2

您忘記檢查您是否已經使用了列表中的所有元素，並且如果已經使用了其他元素，則將其擴展。

Answer 3

爲了使問題稍微更加明顯，想一想如果你的列表最終會被這樣的事情：

right = [1, 2, 3, 4] 
left = [5, 6, 7, 8] 

然後你到達的left結束之前，你會追加所有right - 但是，你會仍然嘗試看看是否會產生你看到的錯誤。您需要添加一個檢查時，其中一個清單耗盡了 - 是這樣的：

if i >= len(right): 
    newArray.extend(left) 
    break 

，同樣爲j >= len(left)情況。