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
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!
Factor-out just the bisect function and get it tested separately from from the "detect duplicates" code which is a separate algorithm.
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
Increase the right index by 1:
right = len(second_list)
Hope this helps out. Good luck :-)