Lecture "Divide and conquer algorithms", exercise 1

[essepuntato]

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.

[diegochillo]

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))

[AleRosae]

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

[fcagnola]

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

[SarahTew]

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))

[laurentfintoni]

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))

[SusannaPinotti]

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))

[giorgiasampo]

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))

[ChiaraCati]

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))

[vanessabonanno]

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

[GiuliaMenna]

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))

[gabrielefiorenza]

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

[ConstiDami]

"""

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))

"""

[LuisAmmi]

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

[SofiBar]

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))

[AlessandroBertozzi]

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))

[AlessandraFa]

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))

[IlaRoss]

# 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))

[edoardodalborgo]

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))

[essepuntato]

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.