Ben Han Ben Han - 9 days ago 4
Python Question

Binary Search Algorithm is not working

So I wrote a binary search algorithm, yet When I do test run it does not work perfectly.

Here is the 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 here is the code for calling the function

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)


The problem is this, I want to add list target_values into the lst correct order when I actually run the function it gives

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]


Which is weird, Its working yet it only fails in the last part of the call
is there any way to fix this problem? Final list should be [1,3,4,5,6,7,8]

As requested I tracked my binary search algorithm, its quiet poor quality. I hope this would help

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

Just change the function to return (-1 * (low+1)) instead:

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))

Output:

('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])

The problem with original implementation was that code assumed mid to be the insertion index but it could never go beyond the current list within the loop as it should when value is inserted to then end of the list.