Binary search stuck in an infinte loop python

Question

My binary search seems to stuck in an infinite loop as it does not output anything for my test data. The second_list is in sorted order and im checking for duplicates from the first list and then adding those duplicates to an empty list. My binary search algorithm performs till there is one element left which I then check is the same as the item, and I would like to keep this structure. I believe the problem is that the right pointer is not decreasing however I cant see why that is.

def detect_duplicates_binary(first_list, second_list):

    duplicates_list = []

    for item in first_list:

        left = 0
        right = len(second_list) - 1

        while left < right:

            midpoint = (left + right) // 2

            if second_list[midpoint] > item:
                right = midpoint - 1
            else:
                left = midpoint

        if (second_list[left] == item):
            duplicates_list.append(item)

    return duplicates_list

You might want to use a [debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) for that or look at [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — Andreas, Aug 23 '19 at 02:26
you can print left , right and midpoint and other you want to see to stdout , then you will find the answer — tinyhare, Aug 23 '19 at 02:53

Raymond Hettinger · Accepted Answer · 2019-08-23T03:49:58.317

Pathology

Here's a possible execution sequence that would result in an infinite loop:

>>> left = 10
>>> right = 11
>>> left < right
True
>>> midpoint = (left + right) // 2
>>> midpoint
10
>>> left = midpoint
>>> left
10
>>> # No change!

Suggestion 1

Factor-out just the bisect function and get it tested separately from from the "detect duplicates" code which is a separate algorithm.

Suggestion 2

Use Python's own bisect module -- it is already tested and documented.

Here's a simplified version of its code:

def bisect_right(a, x):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.
    """
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

Suggestion 3

Increase the right index by 1:

right = len(second_list)

Hope this helps out. Good luck :-)

Binary search stuck in an infinte loop python

1 Answers1

Pathology

Suggestion 1

Suggestion 2

Suggestion 3