Lecture "Divide and conquer algorithms", exercise 1
essepuntato opened this issue · 19 comments
Implement in Python the binary search algorithm – i.e. the recursive function def binary_search(item, ordered_list, start, end)
. It takes an item to search (i.e. item
), an ordered list and a starting and ending positions in the list as input. It returns the position of item
in the list if it is in it, and None
otherwise. The binary search first checks if the middle item of the list between start
and end
(included) is equal to item
, and returns its position in this case. Otherwise, if the middle item is less than item
, the algorithm continues the search in the part of the list that follows the middle item. Instead, in case the middle item is greater than item, the algorithm continues the search in the part of the list that precedes the middle item. Accompany the implementation of the function with the appropriate test cases. As supporting material, Fekete and Morr released a nonverbal definition of the algorithm which is useful to understand the rationale of the binary search steps.
I let a line I used to debug the procedure.
def binary_search(item,ordered_list,start,end):
middle=(end+start)//2
current=ordered_list[middle]
# Debug:
# print ("mid:" + str(middle) + " cur:" + str(current) + " start:" + str(start) +" end:" + str(end))
if current==item:
return middle
else:
if end-start==0:
return None
elif current>item:
return binary_search(item,ordered_list,start,middle-1)
else:
return binary_search(item,ordered_list,middle+1,end)
def test_binary_search(item,ordered_list,start,end, expected):
result=binary_search(item,ordered_list,start,end)
return result==expected
#TEST CASES:
mylist=list([2,4,6,7,9,11])
print(test_binary_search(9,mylist,0,5,4))
print(test_binary_search(4,mylist,0,5,1))
print(test_binary_search(2,mylist,0,5,0))
mylist=list(["beth","jerry","morty","rick","summer"])
print(test_binary_search("rick",mylist,0,4,3))
mylist=list(["lizard","paper","rock","scissors","spock"])
print(test_binary_search("sheldon",mylist,0,4,None))
mylist=[2,3,5,7,11,13,17,19,23,29,31,37]
print(test_binary_search(13,mylist,0,11,5))
This would be my implementation:
def binary_search(item, ordered_list, start, end):
middle = (start+end) // 2
mid_item = ordered_list[middle]
if item == mid_item:
return middle
else:
if item not in ordered_list:
return None
elif mid_item < item:
return binary_search(item, ordered_list, middle, end)
else:
return binary_search(item, ordered_list, start, middle)
def test_binary_search(item, ordered_list, start, end, expected):
return binary_search(item, ordered_list, start, end) == expected
my_list = ["Funerals", "In Rainbows", "Neon Bible", "OK Computer", "Ormai", "Sfortuna", "The Fall of Math", "Wild Light"]
print(test_binary_search("OK Computer", my_list,0,8,3))
print(test_binary_search("Wild Light", my_list,0,8,7))
print(test_binary_search("Unknown Pleasure", my_list,0,8, None))
However, I am not quite sure whether the function should also work with start and end values other than the actual start and end of the list (i.e. more than 0 and less than 8 for my_list
)
For istance print(binary_search("Wild Light", my_list,2,6))
returns the following error RecursionError: maximum recursion depth exceeded in comparison
It took me quite some time but I think I got to a working solution. The test case I used runs the function for each letter of the English alphabet on a list only containing the Italian one. The letters not in the alphabet return "not found" as expected.
def binary_search(item, ordered_list, start, end):
mid = (start + end) // 2 # the middle of the section to be searched is stored in a variable
if item == ordered_list[mid]: # base case: if the item is found in the middle, return item and position
return mid
elif start == mid: # with this line python won't raise RecursionError, if start == middle it means value not in list
return "Value not in list"
elif ordered_list[mid] < item: # if item comes after middle re-run search in the second half of the list
return binary_search(item, ordered_list, mid, end)
elif ordered_list[mid] > item: # if item comes before middle re-run search in the first half of the list
return binary_search(item, ordered_list, start, mid)
ord_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'z']
for i in "abcdefghijklmnopqrstuvwxyz":
print(binary_search(i, ord_list, 0, 21))
# test returns: 0, 1, 2, 3, 4, 5, 6, 7, 8, Value not in list, Value not in list, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, Value not in list, Value not in list, Value not in list, 20
I have a bunch of test cases because as I worked through it I had a bunch of weird problems I didn't understand (including it not working with odd-numbered end
(????) and lots of cases where it seemed to work in most cases but then in running all these test cases I discovered exceptions and had to fix it.
When I got the recursion error in Python Tutor I saw in the step-by-step explanation they give you that I got the error when my start
value became larger than my end
value. I solved that by adding if start > end: return None
at the very beginning.
The one problem I couldn't solve was for it handle empty lists. At one point it was able to return "None" for empty sets but that version of the code couldn't handle looking for things in the first half of an odd-numbered list. I don't know why. If anyone does, let me know. In its current state it works for everything (or so I think) except an empty list, which will give an index error and make it stop running. You'll see I've left my example of that as a comment in the code. If anyone knows how to make it so it can handle an empty list, please let me know. Also is an empty list an unordered list?
If you're having problems and don't know why, doublecheck that your list is actually in order.
def binary_search(item, ordered_list, start, end):
if start > end:
return None
middle = (start + end) // 2
if item == ordered_list[middle]:
return middle
if item < ordered_list[middle]:
return binary_search(item, ordered_list, start, middle-1)
else:
return binary_search(item, ordered_list, middle+1, end)
siblings = ["Lilly", "Sarah", "William"]
family = ["aunt", "father", "grandma", "grandpa", "mother", "uncle"]
alphabet = ["a","b","c","d","e","f"]
empty = []
print(binary_search("Sarah", siblings, 0, 2))
print(binary_search("cousin", family, 0, 5))
print(binary_search("e", alphabet, 0, 5))
#print(binary_search("Sarah", empty, 0, 0))
print(binary_search("William", siblings, 0, 2))
print(binary_search("father", family, 0, 5,))
print(binary_search("b", alphabet, 0, 5))
def test_binary_search(item, ordered_list, start, end, expected):
result = binary_search(item, ordered_list, start, end)
if result == expected:
return True
else:
return False
print(test_binary_search("Sarah", siblings, 0, 2, 1))
print(test_binary_search("cousin", family, 0, 5, None))
print(test_binary_search("e", alphabet, 0, 6, 4))
print(test_binary_search("e", alphabet, 0, 2, None))
print(test_binary_search("b", alphabet, 0, 5, 1))
print(test_binary_search("father", family, 0, 5, 1))
def test_binary_search(item, ordered_list, start, end, expected):
result = binary_search(item, ordered_list, start, end)
if result == expected:
return True
else:
return False
def binary_search(item, ordered_list, start, end):
ordered_list_len = len(ordered_list)
mid = ordered_list_len // 2
if item not in ordered_list:
return None
else:
if ordered_list.index(item) == mid:
return mid
elif ordered_list.index(item) < mid:
binary_search(item, ordered_list[mid:end])
elif ordered_list.index(item) > mid:
binary_search(item, ordered_list[start:mid])
print(test_binary_search('gold digger', ['i', 'aint', 'saying', 'shes', 'a', 'gold digger', 'but', 'she', 'not', 'messin'], 0, 9, 5))
print(test_binary_search('Trinary', ['binary', 'search', 'is', 'a', 'fast', 'algorithm'], 0, 5, 3))
print(test_binary_search('cooking', ['i', 'am', 'cooking', 'chana', 'masala'], 0, 4, 2))
def test_for_binary_search(item, ordered_list, start, end, expected):
return binary_search(item, ordered_list, start, end) == expected
def binary_search(item, ordered_list, start, end):
mid = (start+end) //2
#base case
if start > end:
print(None)
#check if the value in the middle is the item to search
if item == ordered_list[mid]:
return mid
#if item is bigger check values after middle
elif item > ordered_list[mid]:
return binary_search(item, ordered_list, mid, end)
#if item is smaller check values before middle
else:
return binary_search(item, ordered_list, start, mid)
n_list=[1, 3, 13, 23, 27, 36, 45, 72, 101]
l_list=["a", "b", "d", "f", "g", "i"]
italy_list=["Abruzzo", "Basilicata", "Calabria", "Campania", "Emilia Romagna", "Friuli-Venezia Giulia",
"Lazio", "Lombardia", "Marche", "Molise", "Piemonte", "Puglia", "Sardegna", "Sicilia",
"Toscana", "Trentino Alto Adige", "Umbria", "Valle D'Aosta", "Veneto"]
print(test_for_binary_search(23, n_list, 0, 8, 3))
print(test_for_binary_search("f", l_list, 0, 5, 3))
print(test_for_binary_search("Lombardia", italy_list, 0, 19, 7))
def test_binary_search(item,ordered_list,start,end, expected):
result = binary_search(item,ordered_list,start,end)
return result == expected
def binary_search(item, ordered_list, start, end):
work_list = ordered_list[start:end]
mid_position = len(work_list) // 2
if item not in ordered_list:
return None
if ordered_list[start] == item:
return start
if ordered_list[end] == item:
return end
if work_list[mid_position] == item:
return mid_position+start
if work_list[mid_position] <= item:
binary_search(item, ordered_list, start, mid_position)
else:
binary_search(item, ordered_list, mid_position, end)
print (test_binary_search(4,([1,2,3,4,5,6]),1,5, 3))
print (test_binary_search("Carlo",(["Giorgia","Agnese","Carlo","Simone","Stefania","Susanna","Giulia"]),0, 2, 2))
print (test_binary_search("Eloisa",(["Giorgia","Agnese","Carlo","Simone","Stefania","Susanna","Giulia"]),0, 2, None))
def test_binary_search(item, ordered_list, start, end, expected):
result = binary_search(item, ordered_list, start, end)
if result == expected:
return True
else:
return False
def binary_search(item, ordered_list, start, end):
if item in ordered_list:
middle = (start + end) // 2
mid_i = ordered_list[middle]
if item == mid_i:
return middle
elif item != mid_i:
for i1 in ordered_list[:middle]:
if i1 == item:
return ordered_list.index(i1)
for i2 in ordered_list[middle:]:
if i2 == item:
return ordered_list.index(i2)
else:
return 'None'
numbers = [1,2,4,5,6]
words = ['tree', 'pc', 'whale', 'luck']
print(test_binary_search(7, numbers, 0, 4, 'None'))
print(test_binary_search('whale', words, 0, 3, 2))
print(test_binary_search(6, numbers, 0, 4, 4))
print(test_binary_search(7, numbers, 0, 5, 1))
print(test_binary_search('flower', words, 0, 3, 2))
print(test_binary_search('whale', words, 0, 3, 2))
def test_binary_search(item, ordered_list, start, end, expected):
result = binary_search(item, ordered_list, start, end)
if result == expected:
return True
else:
return False
def binary_search(item, ordered_list, start, end):
tot_items = start + (end + 1) # total of the items in list
middle_item_index = tot_items // 2 # find the middle item index
middle_item = ordered_list[middle_item_index] # find middle item value
start_item = ordered_list[start] # what's the starting item of list
end_item = ordered_list[end] # what's the ending item of list
if type(item) != type(middle_item): # check if the type of instances
return None # is different
if item < start_item or item > end_item:
return None # if item searched not in list
if item == middle_item:
return middle_item_index # base case
elif item > middle_item: # search in right part of list
return binary_search(item, ordered_list, middle_item_index, end)
elif item < middle_item: # search in left part of list
return binary_search(item, ordered_list, start, (middle_item_index - 1))
else:
return "Error"
my_ordered_list = ["b", "c", "d"]
my_item = "a"
my_item2 = "d"
print(binary_search(my_item, my_ordered_list, 0, 2)) # None
print(binary_search(my_item2, my_ordered_list, 0, 2)) # 2
# test
print(test_binary_search("a", my_ordered_list, 0, 2, None)) # True
print(test_binary_search("b", my_ordered_list, 0, 2, 0)) # True
print(test_binary_search(3, my_ordered_list, 0, 2, True)) # False
print(test_binary_search(True, my_ordered_list, 0, 2, None)) # True
def test_bin_search(item, ord_list, start,end,expected):
result = bin_search(item, ord_list, start, end)
if expected == result:
return True
else:
return False
def bin_search(item,ord_list, start, end):
middle = len(ord_list) // 2
mid_item = ord_list[middle]
halflist = ()
left = halflist[0:middle]
right = halflist[middle:end]
if item not in ord_list:
return None
if mid_item == item:
return middle
if mid_item < item:
for item in right:
return ord_list.index(item)
if mid_item > item:
for item in left:
return ord_list.index(item)
return ord_list.index(item)
list_n =["a","b","c","d","e","f","g"]
list = [1,2,3,4,5,6,7,8,9]
writers_list = ["Eco", "Faulkner","Roth","Steinbeck","Tolstoj"]
print(test_bin_search("d",list_n,0,6,3))
print(test_bin_search("g",list_n,0,6,6))
print(test_bin_search(9,list,0,8,8))
print(test_bin_search(1,list,0,8,0))
print(test_bin_search("Roth",writers_list,0,4,2))
print(test_bin_search("Calvino",writers_list,0,4,None))
def test_binary_search(item, ordered_list,start,end,expected):
result = binary_search(item, ordered_list, start, end)
return result ==expected
def binary_search(item, ordered_list, start, end):
if item not in ordered_list:
return None
else:
list_used = ordered_list[start:end+1]
middle = len(list_used)//2
if list_used[middle] == item:
return ordered_list.index(list_used[middle])
elif list_used[middle] < item:
return binary_search(item,ordered_list,middle,end)
elif list_used[middle] >item:
return binary_search(item, ordered_list,start, middle)
mylist=list(["carla","giulia","chiara","clara","irene"])
print(test_binary_search("giovanna",mylist, 0, 4, None)) #returns true
mylist1=list(["tablet", "pc", "pen","pencil","room"])
print(test_binary_search("pc",mylist1,0,4,1)) #returns true
"""
def test_binary_search(item, ordered_list, start, end, expected):
return binary_search(item, ordered_list,start, end)==expected
def binary_search(item, ordered_list, start, end):
mid = (end+start) // 2
mid_term = ordered_list[mid]
if mid_term == item:
return mid
elif item > ordered_list[end-1] or item < ordered_list[start]:
return None
elif mid_term < item:
return binary_search(item, ordered_list, mid, end)
else:
return binary_search(item, ordered_list, start, mid)
my_list = [1,3,5,7,8,9]
print(test_binary_search(3, my_list, 0, len(my_list), 1))
print(test_binary_search(9, my_list, 0, len(my_list), 5))
print(test_binary_search(0, my_list, 0, len(my_list), None))
print(test_binary_search(4, my_list, 0, len(my_list), None))
"""
I've not completed the implementation with the test, 'cause the code (that I suppose it's correct) gives me a wrong solution in the second print case. I can't come up with the error in this code. Could you help me, please?
def binary_search(item, ordered_list, start, end):
part_of_list = ordered_list[start:(end + 1)] #the end position is included
mid = len(part_of_list) // 2
if item in part_of_list:
if item == part_of_list[mid]:
return mid
if part_of_list[mid] < item:
binary_search(item, ordered_list, mid, end)
if part_of_list[mid] > item:
binary_search(item, ordered_list, start, mid)
print (binary_search(4,([1,2,3,4,5,6]),1, 5)) # 2
print (binary_search("Leila",(["Fabio", "Federica", "Leila", "Luisa"]),0, 2)). # ?? It should return me "2", but actually it returns "None"
print (binary_search("ciao",(["hola","salut","hello","ciao"]),0, 2)) #none
def test_binary_search(item, ordered_list, start, end, expected):
if binary_search(item, ordered_list, start, end) == expected:
return True
def binary_search(item, ordered_list, start, end):
my_list = ordered_list[start:end]
l = len(my_list)
m = l // 2
left_list = my_list[0:m]
right_list = my_list[m:l]
if item in my_list:
if my_list[m] == item:
return m + start
elif my_list[m] < item:
x = binary_search(item, right_list, 0, len(right_list))
return len(left_list) + x + start
elif my_list[m] > item:
y = binary_search(item, left_list, 0, len(left_list))
return y + start
else:
return None
num_list = [2, 3, 4, 5, 6, 7, 8, 9]
negative_list = [-6, -5, -4, -3, -2, -1, 0]
name_list = ["Andrea", "Davide", "Fabio", "Martina", "Mattia"]
print(test_binary_search(4, num_list, 2, 7, 2))
print(test_binary_search("Martina", name_list, 2, 5, 3))
print(test_binary_search("Martina", name_list, 0, 6, 3))
print(test_binary_search(-6, negative_list, 0, 4, 0))
print(test_binary_search(4, negative_list, 2, 7, None))
def test_binary_search(item, ordered_list, start, end, expected):
result = binary_search(item, ordered_list, start, end)
return result == expected
def binary_search(item, ordered_list, start, end):
my_list = ordered_list[start:end + 1]
position = len(my_list) // 2
# Basic case
if len(my_list) == 1 and item != my_list[position]:
return None
elif item == my_list[position]:
return position
# Divide and conquer
elif item < my_list[position]:
return binary_search(item, my_list, start, position)
else:
return position + binary_search(item, my_list, position, end)
print(test_binary_search(4, [1, 3, 4, 5, 6, 8, 9], 0, 7, 2))
print(test_binary_search(4, [1], 0, 1, None))
print(test_binary_search('g', ['a', 'b', 'c', 'd', 'e', 'f', 'g'], 0, 6, 6))
print(test_binary_search(-1, [-6, -3, -2, -1], 0, 3, 3))
def test_binary_search(item, ordered_list, start, end, expected):
result = binary_search(item, ordered_list, start, end)
return result == expected
def binary_search(item, ordered_list, start, end):
if item not in ordered_list[start:end]:
return None
mid = (start+end) // 2
if item == ordered_list[mid]:
return mid
elif item < ordered_list[mid]:
return binary_search(item, ordered_list, start, mid-1)
elif ordered_list[mid] < item:
return binary_search(item, ordered_list, mid+1, end)
print(test_binary_search(4, [1,3,4,5,7,8,9,11], 1, 7, 2))
print(test_binary_search("m", ["f","n","e","d","a","m","p","t","r","v"], 0, 7, 5))
# tests
def test_binary_search(item, ordered_list, start, end, expected):
result = binary_search(item, ordered_list, start, end)
if result == expected:
return True
else:
return False
# algorithm
def binary_search(item, ordered_list, start, end):
midpos = (start + end) // 2
midel = ordered_list[midpos]
if start < 0:
return 'invalid start value'
if end > len(ordered_list) - 1:
return 'invalid end value'
if start > end:
return 'start cannot be greater than end'
else:
if midel == item:
return midpos
elif start >= end:
return None
elif midel > item:
return binary_search(item, ordered_list, start, midpos-1)
elif midel < item:
return binary_search(item, ordered_list, midpos+1, end)
a = [0, 1, 3, 5, 7, 8, 9]
# some test runs
print(test_binary_search(5, a, 0, 6, 3))
print(test_binary_search(8, a, 0, 6, 5))
print(test_binary_search(1, a, 0, 6, 1))
print(test_binary_search(1, a, 0, 3, 1))
print(test_binary_search(5, a, 4, 2, 'start cannot be greater than end'))
print(test_binary_search(5, a, 2, 7, 'invalid end value'))
print(test_binary_search(5, a, -1, 4, 'invalid start value'))
print(test_binary_search(6, a, 0, 6, None))
def test_binary_search(item, ordered_list, start, end, expected):
return binary_search(item, ordered_list, start, end) == expected
def binary_search(item, ordered_list, start, end):
mid = (start+end) // 2
try:
mid_element = ordered_list[mid]
except IndexError:
return binary_search(item, ordered_list, start, len(ordered_list) - 1)
if item == mid_element:
return mid
if start >= end:
return None
elif item > mid_element:
return binary_search(item, ordered_list, mid+1, end)
else:
return binary_search(item, ordered_list, start, mid-1)
list_test = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'l', 'm']
print(test_binary_search('a', list_test, 2, 9, None))
print(test_binary_search('m', list_test, 0, 40, 10))
print(test_binary_search('d', list_test, 1, 4, 3))
Hi guys,
a few comments about your solutions as follows.
About @AleRosae's comment:
However, I am not quite sure whether the function should also work with start and end values other than the actual start and end of the list (i.e. more than 0 and less than 8 for my_list)
Well, in the recursive step you already do that, right? If you have a maximum recursion depth exceeded in comparison
error when running it, probably it means that you are running too many recursive calls that, for a list like the one you used, is kind of unusual.
About @SarahTew's comment:
The one problem I couldn't solve was for it handle empty lists.
You have to check explicitly if the input list is empty or not before continuing, and then return None
if that is the case. I've updated the solution of the exercise online so as to consider also this situation, which is totally reasonable indeed.
About @giorgiasampo, @ChiaraCati, @laurentfintoni, @GiuliaMenna, @gabrielefiorenza, @LuisAmmi, @SofiBar and @AlessandraFa's code:
item not in ordered_list # or something similar
Doing that is kind of cheating since you are checking if the item is in the list before looking for it. But the binary search should not know that in advance: it should return None
if the process does not find the specific item - similarly to the way the linear_search
works, which returns None
if the item was not found.