I'm working on an implementation of binary search (in Python) that can operate on a sorted array that may have duplicate elements. I've written a submission that has managed to hold up against my test cases so far, but I have the feeling that there may be a more elegant way to write my recursive solution.
EDIT:
In response to @SylvainD, I've rewritten my code. I had some ideas on how to improve it in the past several hours, and I've included some new test cases based on the array @SylvainD provided in his/her comment.
It's passing every test case I have so far except for when I ask the function to search for all occurrences of '6' in the array provided by @SylvainD. For some reason, it's stopping short of the last index.
def binary_search(keys, target, start = 0, end = None):
'''
Searches the array, 'keys', for an integer, 'target'. Each
call of the method also takes a 'start' and 'end' argument,
specifying the index to start and end the search on.
If the target is found to be in the keys array, the index of
its location is returned. If not, a -1 is returned.
'''
if end == None: # If end is set to a default argument of 'None', then set it to the index of the last element in the array, 'keys'.
end = len(keys)-1
if end < start: # If the last element is smaller than the first, then the array becomes valid because it is not sorted.
return -1
mp = start+(end-start)//2 # Calculate the midpoint
if target == keys[mp]: # Is the target at mp?
return mp
elif target < keys[mp]: # target is below the mp
return binary_search(keys, target, start = start, end = mp-1)
else:
return binary_search(keys, target, start = mp+1, end=end)
def left_finder(keys, target, start = 0, end = None):
'''Find the index of the left most target in a sorted array with duplicates'''
if end == None:
end = len(keys)-1
mp = binary_search(keys, target) # call binary search
if mp==0 or mp==-1: # mp is 1st element or DNE in keys
return mp
elif keys[mp-1] != target: # Left neighbor != target
return mp
else: # Keep searching moving left by shrinking end by one
return binary_search(keys, target, start=start, end=mp-1)
def right_finder(keys, target, start=0, end=None):
'''Find the index of the rightmost target in the sorted array with duplicates'''
if end == None:
end = len(keys)-1
mp = binary_search(keys, target)
if mp == len(keys)-1 or mp == -1: # mp is last element or DNE
return mp
elif keys[mp+1] != target: # Not last element, right neighbors != target
return mp
else: #keep searching pushing right ward
return binary_search(keys, target, start = mp+1, end=end)
def duplicate_binary_search(keys, target):
'''Uses left finder, right finder, and binary search to find all occurrences of a target in keys'''
all_occurrences = [] # container for situations with multiple occurrences of the target
left = left_finder(keys, target) # find a value in keys that qualifies as a possible left
right = right_finder(keys, target) # find a value in keys that qualifies as possible right
if left == right: # check if there is only 1 occurrence, or if target DNE in keys
return left
else: # append indices of all occurrences to list and return
for i in range(left, right+1_:
all_occurrences.append(i)
return all_occurrences
In a nutshell, I'm piggybacking off of my binary search solution for sorted arrays with no duplicates. I'm call this binary search method in functions Left Finder and Right Finder, to try and find the left and right indices. I then return the range of indices for which the duplicate elements are found.
Test Four is currently failing. I suspect that maybe just re-calling my original solution might be too crude, and I may need to re-imagine a Right Finder binary search from the ground up.
import unittest
class TestBinarySearch(unittest.TestCase):
def test_one(self):
keys = [1, 13, 42, 42, 42, 77, 78]
target = 42
results = duplicate_binary_search(keys, target)
self.assertListEqual(results, [2, 3, 4])
def test_two(self):
keys = [1, 2, 3, 4, 4, 4, 5, 5, 6, 6, 6]
target = 4
results = duplicate_binary_search(keys, target)
self.assertListEqual(results, [3, 4, 5])
def test_three(self):
keys = [1, 2, 3, 4, 4, 4, 5, 5, 6, 6, 6]
target = 5
results = duplicate_binary_search(keys, target)
self.assertListEqual(results, [6,7])
def test_four(self):
# Right most is last element
# This test currently fails to realize 10 as right most
keys = [1, 2, 3, 4, 4, 4, 5, 5, 6, 6, 6]
target = 6
results = duplicate_binary_search(keys, target)
self.assertListEqual(results, [8, 9, 10])
def test_five(self):
# Left most is first element
keys = [1, 1, 1, 4, 4, 4, 5, 5, 6, 6, 6]
target = 1
results = duplicate_binary_search(keys, target)
self.assertListEqual(results, [0, 1, 2])
```
