Comments (19)
diegochillo
commented on August 27, 2024
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))
from 2020-2021.
AleRosae
commented on August 27, 2024
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
from 2020-2021.
fcagnola
commented on August 27, 2024
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
from 2020-2021.
SarahTew
commented on August 27, 2024
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))
from 2020-2021.
laurentfintoni
commented on August 27, 2024
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))
from 2020-2021.
SusannaPinotti
commented on August 27, 2024
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))
from 2020-2021.
giorgiasampo
commented on August 27, 2024
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))
from 2020-2021.
ChiaraCati
commented on August 27, 2024
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))
from 2020-2021.
vanessabonanno
commented on August 27, 2024
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
from 2020-2021.
GiuliaMenna
commented on August 27, 2024
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))
from 2020-2021.
gabrielefiorenza
commented on August 27, 2024
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
from 2020-2021.
ConstiDami
commented on August 27, 2024
"""
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))
"""
from 2020-2021.
LuisAmmi
commented on August 27, 2024
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
from 2020-2021.
SofiBar
commented on August 27, 2024
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))
from 2020-2021.
AlessandroBertozzi
commented on August 27, 2024
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))
from 2020-2021.
AlessandraFa
commented on August 27, 2024
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))
from 2020-2021.
IlaRoss
commented on August 27, 2024
# 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))
from 2020-2021.
edoardodalborgo
commented on August 27, 2024
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))
from 2020-2021.
essepuntato
commented on August 27, 2024
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.
from 2020-2021.
Related Issues (20)
- Lecture "Brute-force algorithms", exercise 5 HOT 15
- Lecture "Organising information: unordered structures", exercise 1 HOT 21
- Lecture "Organising information: unordered structures", exercise 2 HOT 19
- Lecture "Organising information: unordered structures", exercise 3 HOT 20
- Lecture "Recursion", exercise 1 HOT 19
- Lecture "Recursion", exercise 2 HOT 20
- Lecture "Divide and conquer algorithms", exercise 2 HOT 17
- Lecture "Divide and conquer algorithms", exercise 3 HOT 5
- Lecture "Dynamic programming algorithms", exercise 1 HOT 21
- Lecture "Dynamic programming algorithms", exercise 2 HOT 19
- Lecture "Organising information: trees", exercise 1 HOT 9
- Lecture "Organising information: trees", exercise 2 HOT 7
- Bonus exercise (AtariGo) HOT 2
- Lecture "Backtracking algorithms", exercise 1 HOT 6
- Lecture "Backtracking algorithms", exercise 2 HOT 5
- Lecture "Organising information: graphs", exercise 1 HOT 15
- Lecture "Organising information: graphs", exercise 2 HOT 14
- Lecture "Greedy algorithms", exercise 1 HOT 5
- Lecture "Greedy algorithms", exercise 2 HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from 2020-2021.