Ben Han - 7 months ago 38

Python Question

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.

Source (Stackoverflow)