Ben Han - 1 year ago 63
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]
``````

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download