Lecture "Divide and conquer algorithms", exercise 1

[essepuntato]

Implement the binary search algorithm in Python – 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 central item is less than item, the algorithm continues the search in the part of the list that follows the middle item. Instead, if the central item is greater than item, the algorithm continues the search in the part of the list preceding the central 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 [Fekete, Morr, 2018a], which is useful to understand the rationale of the binary search steps.

[delete4ever]

# Test case for the algorithm
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
# Code for the algorithm
def binary_search(item, ordered_list, start, end):
    if end >= start:
        mid = (start+end) // 2
        if ordered_list[mid] == item:
            return mid
        elif ordered_list[mid] < item:
            return binary_search(item, ordered_list, mid+1, end)
        else:
            return binary_search(item, ordered_list, start, mid-1)
    else:
        return None
# Three test runs
print(test_binary_search(4, [1, 2, 3, 4, 5 ,6], 0, 5, 3)) #True
print(test_binary_search(1, [2, 3, 4, 5], 0, 3, None)) #True
print(test_binary_search(1, [1], 0, 0, 0)) #True

[SleepingSteven]

def test (lista, term, pos):
    if binary_search(lista, term, 0, len(lista)) == pos:
        return True
    else:
        return False

def binary_search (list, term, start, end):
    new_list_len = len(list[start:end])
    mid = start+new_list_len//2
    if list[mid] == term:
        if list[mid] == term:
            return mid+1 
    elif list[mid] > term:
        return binary_search (list, term, start, mid)
    else:
        return binary_search (list, term, mid, end)   

lista = [1,2,5,7,9,12,15]

print(test(lista,5,3)) 

[leonardozilli]

def test_binary_search(item, ordered_list, start, end, expected_result):
    result = binary_search(item, ordered_list, start, end)
    return result == expected_result

def binary_search(item, ordered_list, start, end):
    middle_item = ordered_list[(start + end) // 2]

    if item in ordered_list[start:end + 1]:
        if middle_item == item:
            return ordered_list.index(middle_item)
        elif middle_item < item:
            return binary_search(item, ordered_list, ordered_list.index(middle_item) + 1, end)
        elif middle_item > item:
            return binary_search(item, ordered_list, start, ordered_list.index(middle_item) - 1)
    else:
        return None


print(test_binary_search(3 , [1, 2, 3, 4, 5, 6, 7, 8, 9], 2, 6, 2))
print(test_binary_search('b', ['a', 'b', 'c', 'd', 'e', 'f'], 1, 3, 1))
print(test_binary_search(4, [1, 2, 3, 4, 5 ,6], 4, 5, None))
print(test_binary_search(1, [2, 3, 4, 5], 0, 3, None)) 
print(test_binary_search(1, [1], 0, 0, 0))

[ranacoskun]

def test_binary_search(item, ordered_list, start, end, expected):
    if expected == binary_search(item, ordered_list, start, end):
        return True
    else:
        return False


def binary_search(item, ordered_list, start, end):
    while len(ordered_list) > 0 and start <= end:
        mid = (start + end) // 2
        if item == ordered_list[mid]:
            return mid
        elif ordered_list[mid] < item:
            return binary_search(item, ordered_list, mid + 1, end)
        else:
            return binary_search(item, ordered_list, start, mid - 1)


print(test_binary_search(4, [0, 2, 3, 5, 7, 8, 9], 0, 6, None))  # True
print(test_binary_search(8, [0, 2, 3, 5, 7, 8, 9], 0, 6, 5))  # True
print(test_binary_search(8, [0, 2, 3, 5, 7, 8, 9], 0, 3, None))  # True
print(test_binary_search(8, [], 0, 3, None))  # True
print(test_binary_search('f', ['a', 'b', 'c', 'd', 'e', 'f'], 0, 5, 5))  # True

[lucia1299]

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 start<=end:
        mid = (start+end) // 2
        if ordered_list[mid] == item:
            return mid         
        elif ordered_list[mid] < item:
            return binary_search(item, ordered_list, start+1, end)
        elif ordered_list[mid] > item:
            return binary_search(item, ordered_list, start, end-1)
    else:
        return None

print(test_binary_search("Bologna", ["Bologna", "Firenze", "Milano", "Roma"], 0, 3, 0)) #True
print(test_binary_search("Milano", ["Bologna", "Firenze", "Milano", "Roma"], 0, 3, 2)) #True
print(test_binary_search(2, [0, 1, 2, 3, 4, 5], 0, 5, 2)) #True
print(test_binary_search("Palermo", ["Bologna", "Firenze", "Milano", "Roma"], 0, 3, None)) #True

[EricaAndreose]

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):
    longness = start + (end+1)
    mid = longness // 2
    if item in ordered_list:
        if item == ordered_list[mid]:
            return mid
        elif ordered_list[mid] < item:
            return binary_search(item, ordered_list, mid+1, end)
        elif ordered_list[mid] > item:
            return binary_search(item, ordered_list, start, mid-1)
    else:
        return None 

print(test_binary_search("Ciao", ["Bella", "Ciao", "Miao", "Sole"], 0, 3, 1))
print(test_binary_search("Bella", ["Bella", "Ciao", "Miao", "Sole"], 0, 3, 0))
print(test_binary_search("Sole", ["Bella", "Ciao", "Miao", "Sole"], 0, 3, 3))
print(test_binary_search("_", ["Bella", "Ciao", "_", "Sole"], 0, 3, 2))
print(test_binary_search("Anna", ["Bella", "Ciao", "Miao", "Sole"], 0, 3, None))
print(test_binary_search(1, [0, 1, 2, 3], 0, 3, 1))
print(test_binary_search(0, [0, 1, 2, 3], 0, 3, 0))
print(test_binary_search("a", ["a", "b", "c", "d"], 0, 3, 0))
print(test_binary_search("b", ["a", "b", "c", "d"], 0, 3, 1))
print(test_binary_search("s", ["a", "b", "c", "d"], 0, 3, None))
print(test_binary_search("i", ["i", "i", "i", "i"], 0, 3, 2))

[n1kg0r]

def test_binary_search(item, ordered_list, start, end, expected):
    return expected == binary_search(item, ordered_list, start, end)

def binary_search(item, ordered_list, start, end):
    if start > end or len(ordered_list) < end or len(ordered_list) == 0:
        return None
    if item == ordered_list[(start + end) // 2]:
        return (start + end) // 2
    elif item > ordered_list[(start + end) // 2]:
        return binary_search(item, ordered_list, (start + end) // 2 + 1, end)
    elif item < ordered_list[(start + end) // 2]:
        return binary_search(item, ordered_list, start, (start + end) // 2 - 1)
    
print(test_binary_search(3, [1, 2, 3, 4, 5], 0, 4, 2))
print(test_binary_search("Denver", ["Alice", "Bob", "Catherine", "Charles"], 0, 3, None))
print(test_binary_search("Harry", ["Harry", "Hermione", "Ron"], 0, 2, 0))
print(test_binary_search("Harry", [], 0, 0, None))

[ChiaraParravicini]

def binary_search(item, ordered_list, start, end):
    mid = (start+end)//2
    if start <= end:
        if ordered_list[mid] == item:
            return mid
        elif ordered_list[mid] < item:
            start = mid + 1
            return binary_search(item, ordered_list, start, end)
        elif ordered_list[mid] > item:
            end = mid - 1
            return binary_search(item, ordered_list, start, end)
    else:
        return None


print(test_binary_search("d", ["a", "b", "c", "d", "e", "f"], 0, 5, 3))
print(test_binary_search("d", ["a", "b", "c", "d", "d"], 0, 4, 3))
print(test_binary_search("d", ["a", "b", "c", "c", "e"], 1, 4, None))
print(test_binary_search(5, [0, 1, 1, 2, 5, 7], 3, 5, 4))

[alka2696]

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 start > end:
        return None

    mid = (start + end) // 2

    if ordered_list[mid] == item:
        return mid

    elif ordered_list[mid] < item:
        return binary_search(item, ordered_list, mid + 1, end)

    else:
        return binary_search(item, ordered_list, start, mid - 1)

ordered_list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

print(test_binary_search(9, ordered_list, 0, len(ordered_list) - 1, 4)) #True
print(test_binary_search(1, ordered_list, 0, len(ordered_list) - 1, 0)) #True
print(test_binary_search(19, ordered_list, 0, len(ordered_list) - 1, 9)) #True
print( test_binary_search(10, ordered_list, 0, len(ordered_list) - 1, None) #True