CODEWITHSUNDEEP
pythonalgorithmbinary-search
Dongho Han
Dongho Han

Reputation: 97

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]

Upvotes: 1

Views: 89

Answers (2)

niemmi
niemmi

Reputation: 17263

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 the end of the list.

Upvotes: 3

Prune
Prune

Reputation: 77837

I think I got it. Put in the print statements I recommended. Track especially the insertion at the end of the existing list. I believe that you'll find that you can't drive low high enough to provoke inserting at the end of the list; the most you can get is to insert before the final element, which is just what's happening in your test.

Upvotes: 0

Related Questions