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.

[Postitisnt]

#function
def binary_search(item, ordered_list, start, end):
    if len(ordered_list) == 1:
        return ordered_list.index(item)
    else:
        #the +1 is intended to include the last index reference of the end
        insideTheList = ordered_list[start : end +1] 
        length = len(insideTheList)
        mid = length // 2
        newMid = ordered_list.index(insideTheList[mid])
        if item in insideTheList:
            if item == insideTheList[mid]:
                return ordered_list.index(item)
            elif item > insideTheList[mid]:
                return binary_search(item, ordered_list, newMid, end)
            elif item < insideTheList[mid]:
                return binary_search(item, ordered_list, start, newMid-1)
        else:
            return None

#test
def testCase(item, inputList, start, end, expected):
    if binary_search(item, inputList, start, end) == expected:
        print("The result is correct!")
        return True
    else:
        return False
        print("Try again")

#      0   1   2   3   4   5   6   7   8
li = ['a','b','c','d','e','f','g','h','i'] #len = 9
#mid = 4  sta  i      mid     end     

item1 = 'c'
startingPoint1 = 1
endingPoint1 = 7
#expected = 1
print("Test 1 ------->",testCase(item1, li, startingPoint1, endingPoint1, 2))

item2 = 'g'
startingPoint2 = 2
endingPoint2 = 8
#expected = 6
print("Test 2 ------->", testCase(item2, li, startingPoint2, endingPoint2, 6))

item3 = 'c'
startingPoint3 = 0
endingPoint3 = 5
#expected = 2
print("Test 3 ------->", testCase(item3, li, startingPoint3, endingPoint3, 2))

item4 = 'y'
startingPoint4 = 1
endingPoint4 = 6
#expected = None
print("Test 4 ------->", testCase(item4, li, startingPoint4, endingPoint4, None))

[tommasobattisti]

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

binary_search_list = ['b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l']

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

print(test_binary_search('a', binary_search_list, 0, len(binary_search_list)-1, None))
print(test_binary_search('b', binary_search_list, 0, len(binary_search_list)-1, 0))
print(test_binary_search('c', binary_search_list, 0, len(binary_search_list)-1, 1))
print(test_binary_search('d', binary_search_list, 0, len(binary_search_list)-1, 2))
print(test_binary_search('e', binary_search_list, 0, len(binary_search_list)-1, 3))
print(test_binary_search('f', binary_search_list, 0, len(binary_search_list)-1, 4))
print(test_binary_search('g', binary_search_list, 0, len(binary_search_list)-1, 5))
print(test_binary_search('h', binary_search_list, 0, len(binary_search_list)-1, 6))
print(test_binary_search('i', binary_search_list, 0, len(binary_search_list)-1, 7))
print(test_binary_search('j', binary_search_list, 0, len(binary_search_list)-1, 8))
print(test_binary_search('k', binary_search_list, 0, len(binary_search_list)-1, 9))
print(test_binary_search('l', binary_search_list, 0, len(binary_search_list)-1, 10))
print(test_binary_search('s', binary_search_list, 0, len(binary_search_list)-1, None))

[MaddaGh]

This solution seems to work but it feels way to complicated to be the right one, I tried a simpler solution before but, even it it seemed to work well when working on the left side of the list, I couldn't get the right index when it worked on the right side of the list. I proceeded trying to solve this issue and this is where I ended up.

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

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

print(test_binary_search("moscow mule", ["americano", "bellini", "dry martini", "gin tonic", "long island", "moscow mule"], 0, 5, 5))
print(test_binary_search("white russian", ["americano", "bellini", "dry martini", "gin tonic", "long island", "moscow mule"], 0, 6, None))
print(test_binary_search(5, [1, 2, 4, 5, 6, 8, 9, 10, 14, 25, 34, 56], 0, 11, 3))
print(test_binary_search("ciliega", ["arancia", "anguria", "banana", "ciliega", "kiwi", "mango", "mela", "mirtillo", "papaya", "pera"], 0, 9, 3))
print(test_binary_search("mirtillo", ["arancia", "anguria", "banana", "ciliega", "kiwi", "mango", "mela", "mirtillo", "papaya", "pera"], 0, 9, 7))

[ManueleVeggi]

def test_binsearch(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 end > start and len(ordered_list) > 0:
        mid_index = (start+end)//2
        mid_item  = ordered_list[mid_index]
        if  item == mid_item:
            return mid_index
        elif item < mid_item:
            return binary_search(item, ordered_list, start, mid_index)
        elif item > mid_item:
            return binary_search(item, ordered_list, mid_index, end)
        else:
            return None

l = [0,1,2,3,4,5,6,7,8,9]

print(test_binsearch(7, l, 5, 9, 7))
print(test_binsearch(6, l, 5, 9, 6))
print(test_binsearch(8, l, 5, 9, 8))
print(test_binsearch(4, l, 5, 9, None))

The result is

True
True
True
True

[RebeccaJillianBeattie]

[CarmenSantaniello]

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

def binary_search(item, ordered_list, start, end):
    if end > start and len(ordered_list) > 0:  
        mid_index = (start+end) // 2
        mid_item = ordered_list[mid_index]
        if mid_item == item:
            return mid_index
        elif mid_item < item:
            return binary_search(item, ordered_list, mid_index, end)
        elif mid_item > item:
            return binary_search(item, ordered_list, start, mid_index)
        else:
            return None

print(test_binary_search(2,[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 0, 4, 2))
print(test_binary_search(8,[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 5, 9, 8))
print(test_binary_search(3,[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 5, 9, None))
print(test_binary_search("Bulbasaur", ["Abra", "Bulbasaur", "Venusaur", "Charmander", "Squirtle", "Butterfree", "Weedle", "Chikorita", "Charmeleon", "Psyduck"],0,3,1))
print(test_binary_search("Weedle", ["Abra", "Bulbasaur", "Venusaur", "Charmander", "Squirtle", "Butterfree", "Weedle", "Chikorita", "Charmeleon", "Psyduck"],3,9,6))
print(test_binary_search("Alakazam", ["Abra", "Bulbasaur", "Venusaur", "Charmander", "Squirtle", "Butterfree", "Weedle", "Chikorita", "Charmeleon", "Psyduck"],3,9,None))

It returns:

True
True
True
True
True
True

[ghasempouri1984]

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

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

print(test_binary_search("N", [], 0, 0, None))
print(test_binary_search(4, [1, 2, 3, 4, 5, 6, 7], 0, 3, 3))
print(test_binary_search(4, [1, 2, 3, 4, 5, 6, 7], 0, 6, 3))
print(test_binary_search("d", ["A", "B", "C", "Cd", "ha"], 0, 3, None))
print(test_binary_search("V", ["V", "W", "Z"], 0, 2, 0))

[chloeppd]

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

def binary_search(item, ordered_list, start, end):
    len_of_positions = start+end  

    mid_of_list = len_of_positions // 2
    if item  in ordered_list:

        if item == ordered_list[mid_of_list]:
            return ordered_list.index(item)

        elif item > ordered_list[mid_of_list]:
            return binary_search(item, ordered_list, mid_of_list, end+1)

        elif item<ordered_list[mid_of_list]:
            return binary_search(item, ordered_list, start, mid_of_list-1)  

    else: return None

list= ["a", "b", "c", "d", "e", "f"]

print(test_binary_search("a", list, 0, 5, 0))
print(test_binary_search("g", list, 0, 5, None))
print(test_binary_search("c", list, 0, 1, 2))
print(test_binary_search("f", list, 0, 5, 5))

[Bianca-LM]

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

print(test_binary_search(5, [1, 3, 4, 6 , 7, 8, 10, 21], 0, 7, None))
print(test_binary_search(6, [1, 3, 4, 6 , 7, 8, 10, 21], 0, 7, 3))
print(test_binary_search(21, [1, 3, 4, 6 , 7, 8, 10, 21], 0, 7, 7))
print(test_binary_search(21, [], 0, 7, None))
print(test_binary_search(1, [1], 0, 0, None))

[federicabonifazi]

first_test=[2, 4, 5, 8, 9, 12, 15, 16]
second_test=["american god", "coraline", "good omens",  "neverwhere"]
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 not in ordered_list:
        return None
    elif len(ordered_list) == 1:
        if item in ordered_list:
            return ordered_list.index(item)
    elif len(ordered_list)>1:
        mid = len(ordered_list) // 2
        mid_item = ordered_list[mid]
        if item == mid_item:
            return mid
        else:
            if mid_item < item:
                right_list = []
                right_list=ordered_list[mid:end+1]
                binary_search(item, right_list, mid, end+1)
                return right_list.index(item) + mid
            else:
                left_list = []
                left_list = ordered_list[:mid+1]
                binary_search(item, left_list, start, mid+1)
                return left_list.index(item)

print(test_binary_search(8, first_test, 0, 7, 3 ))
print(test_binary_search(12, first_test, 0, 7, 5))
print(test_binary_search(21, first_test, 0, 7, None))
print(test_binary_search("good omens", second_test, 0, 4, 2))

[olgagolgan]

[angstigone]

[AmeliaLamargese]

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

test_binary_search("ciao", ["hello", "ciao", "salut"], 0, 2, 1)
test_binary_search( 5, [2, 3, 5, 7, 9], 0, 4, 2)
test_binary_search( 5, [2, 3, 5, 7, 9], 0, 1, None)
test_binary_search( 6, [2, 3, 5, 7, 9], 0, 4, None)

[essepuntato]

Hi all,

A few suggestions and tests you should try on your code:

• What happens if the input list is empty? Does it return the expected value (i.e. None)?
• What if start == end, i.e. when there is only one item in the list, and the item is the correct one, e.g. binary_search("a", ["a"], 0, 0)?
• When you are in the recursive step, you can exclude the item in mid from the next check since it has been already checked.
• A reminder: the element at start and end positions are included in the search. What happens running binary_search("e", ["a", "b", "c", "d", "e"], 0, 4)?
• During the execution of the function, the input list never changes – no need to create a sublist, but use start and end to access the portion of the input list of interest.
• The method index of lists should not be used since it does exactly what binary_search should return – and, after all, you already have your candidate index in mid.

[teragramgius]

Following the non-verbal definition of the "binary search" algorithm provided by Fekete and Morr, at first, I was tempted to create a sublist, but then I discovered thet it could be more useful to change the mid value time by time (i.e. with the recursive operations), so I attached as mantra the suggestion of professor Peroni.

Let's dive in the exercise.

BASE-CASE The input item corresponds to the mid item of the ordered_list

DIVIDE If the base case doesn't happen, then we have to change the middle value, according to the fact that the value of the previous mid is greater of lower then the value we're searching for (i.e. item)

CONQUER Run the same algorithm recursively on these two amounts of input

COMBINE The values are combined to provide the final solution

#inputs: 
# 1. An item to search for in the sorted_list
# 2. The sorted list
# 3. The starting value of the sorted_list
# 4. The ending value of the sorted_list

#output:  Returns the position of item in the list if it is in it and None otherwise.  

Answer: running the binary_search("e", ["a", "b", "c", "d", "e"], 0, 4), it returns 4.

[sanyuezoe]

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

def binary_search(item, ordered_list, start, end):
    len_list = len(ordered_list)
    mid = (start + end) // 2
    if item not in ordered_list:
        return None
    if len_list == 1 and ordered_list[0] == item:
        return ordered_list.index(item)
    elif len_list > 1:
        if ordered_list[mid] == item:
            return mid
        elif ordered_list[mid] > item:
            return binary_search(item, ordered_list[start:mid], start, mid)
        else:
            return binary_search(item, ordered_list[mid:end], mid, end)

print(binary_search_test(4, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 0, 9, 4))
print(binary_search_test('你好', ['今天', '你好', '天气', '很好', '我好困'], 0, 4, 1))
print(binary_search_test('fvdsf', [0,5, 645, 7842216, 45], 0, 4, None))
print(binary_search_test('dog', [51, 'cat', 'dog', 346, 482], 0, 4, 2))