Binärsuchalgorithmus funktioniert nicht

Question

So schrieb ich einen binären Suchalgorithmus, noch, wenn ich Testlauf es funktioniert nicht perfekt.

Hier ist der Code

def binarySearch(lst, target): 
    low = 0 
    high = len(lst)-1 
    while high >= low: 
     mid = (high + low)//2 
     if target < lst[mid]: 
      high = mid - 1 
     elif target > lst[mid]: 
      low = mid + 1 
     else: 
      return mid 

    return (-1 * (mid+1)) 

abd hier der Code ist die Funktion

lst_test = [3, 4, 6, 7] 
target_values = [1, 3, 5, 8] 

for t in target_values: 
    i = binarySearch(lst_test, t) 
    if (i < 0): 
     print("In", lst_test, t, "is going to be inserted at index",-1*(i+1)) 
     lst_test.insert((i+1)*-1, t) 
    else: 
     print("In", lst_test, t, "was found at index", i) 
print("The final list is:", lst_test) 

Das Problem dieser für den Aufruf ist, möchte ich Liste target_values ​​in die lst richtigen Reihenfolge, wenn ich tatsächlich hinzufügen führen sie die Funktion gibt es

In [3, 4, 6, 7] 1 is going to be inserted at index 0 
In [1, 3, 4, 6, 7] 3 was found at index 1 
In [1, 3, 4, 6, 7] 5 is going to be inserted at index 3 
In [1, 3, 4, 5, 6, 7] 8 is going to be inserted at index 5 
The final list is: [1, 3, 4, 5, 6, 8, 7] 

Welche seltsam ist, seine Arbeit doch nur f ails im letzten Teil des Anrufs gibt es eine Möglichkeit, dieses Problem zu beheben? Die endgültige Liste sollte [1,3,4,5,6,7,8] sein.

Wie angefordert, verfolgte ich meinen binären Suchalgorithmus, seine ruhige schlechte Qualität. Ich hoffe, das würde helfen

Mid point is: 1 
target value is smaller than a mid point 
Mid point is: 0 
target value is smaller than a mid point 
In [3, 4, 6, 7] 1 is going to be inserted at index 0 
Mid point is: 2 
target value is smaller than a mid point 
Mid point is: 0 
target value is larger than a mid point 
Mid point is: 1 
Found the index location at 1 
In [1, 3, 4, 6, 7] 3 was found at index 1 
Mid point is: 2 
target value is larger than a mid point 
Mid point is: 3 
target value is smaller than a mid point 
In [1, 3, 4, 6, 7] 5 is going to be inserted at index 3 
Mid point is: 2 
target value is larger than a mid point 
Mid point is: 4 
target value is larger than a mid point 
Mid point is: 5 
target value is larger than a mid point 
In [1, 3, 4, 5, 6, 7] 8 is going to be inserted at index 5 
The final list is: [1, 3, 4, 5, 6, 8, 7] 

Answer 1

einfach die Funktion ändern (-1 * (low+1)) stattdessen zurück:

def binarySearch(lst, target): 
    low = 0 
    high = len(lst)-1 
    while high >= low: 
     mid = (high + low)//2 
     if target < lst[mid]: 
      high = mid - 1 
     elif target > lst[mid]: 
      low = mid + 1 
     else: 
      return mid 

    return (-1 * (low+1)) 

Ausgang:

('In', [3, 4, 6, 7], 1, 'is going to be inserted at index', 0) 
('In', [1, 3, 4, 6, 7], 3, 'was found at index', 1) 
('In', [1, 3, 4, 6, 7], 5, 'is going to be inserted at index', 3) 
('In', [1, 3, 4, 5, 6, 7], 8, 'is going to be inserted at index', 6) 
('The final list is:', [1, 3, 4, 5, 6, 7, 8]) 

Das Problem mit Original-Implementierung war, dass Code mid angenommen das Einfügen Index zu sein, aber es könnte nie über das hinausgehen Die aktuelle Liste in der Schleife, wie sie sollte, wenn der Wert am Ende der Liste eingefügt wird.

Answer 2

Ich denke, ich habe es. Setzen Sie die von mir empfohlenen Druckanweisungen ein. Verfolgen Sie insbesondere die Einfügung am Ende der bestehenden Liste. Ich glaube, Sie werden feststellen, dass Sie niedrig nicht hoch genug fahren können, um das Einfügen am Ende der Liste zu provozieren; Das Beste, was Sie bekommen können, ist vor das letzte Element, was gerade in Ihrem Test passiert.