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.

[ereuhl]

My solution:

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

The same but with a lot of console output to easier understand the execution of the algorithm:

def binary_search(item, ordered_list, start, end):
    middle = int((start+end) / 2)
    print("\nStarting a binary search.",
          "\n--> Parameters: item:", item, "\t ordered_list:", ordered_list, "\t start:", start, "\t end:", end,
          "\n--> Currently regarded list: ", ordered_list[start:end + 1],
          "\n--> Middle item of the current list:", ordered_list[middle])

    if start > end:
        print("\n--> The value of start is bigger than end.",
              "\n--> Result: The item was not found.")
        return None

    print("Checking the middle item of the current list against the searched item.")
    if ordered_list[middle] == item:
        print("--> Result: The item was found at position", middle, "of the input list.")
        return middle
    elif ordered_list[middle] < item:
        print("--> The searched item is larger than the current middle item.",
              "\n--> Continue the search in the larger part of the current list.")
        return binary_search(item, ordered_list, middle+1, end)
    elif ordered_list[middle] > item:
        print("--> The searched item is smaller than the current middle item.",
              "\n--> Continue the search in the smaller part of the current list.")
        return binary_search(item, ordered_list, start, middle-1)
    else:
        print("--> Result: The item was not found.")
        return None

Test cases:

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

test_list = [0, 10, 20, 30, 40, 50, 60]
print("\nTest 1 -->", test_binary_search(30, test_list, 0, 6, 3), "\n")  # True
print("\nTest 2 -->", test_binary_search(30, test_list, 0, 2, None), "\n")  # True
print("\nTest 3 -->", test_binary_search(30, test_list, 3, 6, 3), "\n")  # True
print("\nTest 4 -->", test_binary_search(70, test_list, 0, 6, None), "\n")  # True
print("\nTest 5 -->", test_binary_search(0, test_list, 0, 6, 0), "\n")  # True
print("\nTest 6 -->", test_binary_search(10, test_list, 0, 6, 1), "\n")  # True
print("\nTest 7 -->", test_binary_search(60, test_list, 0, 6, 6), "\n")  # True
print("\nTest 8 -->", test_binary_search(50, test_list, 0, 6, 5), "\n")  # True
print("\nTest 9 -->", test_binary_search(-10, test_list, 0, 4, None), "\n")  # True
print("\nTest 10 -->", test_binary_search(10, test_list, 0, 1, 1), "\n")  # True

[FrancescoFernicola]

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

num_list = [2, 4, 8, 16, 32, 64, 128]
FF_list = ["Auron", "Cid", "Kefka", "Sephirot", "Squall", "Terra", "Vivi", "Zidane"]
print(test_binary_search(64, num_list, 0, 6, 5))
print(test_binary_search(16, num_list, 0, 6, 3))
print(test_binary_search(4, num_list, 0, 6, 1))
print(test_binary_search(128, num_list, 0, 6, 6))
print(test_binary_search(2, num_list, 0, 6, 0))
print(test_binary_search(42, num_list, 0, 7, None))
print(test_binary_search("Auron", FF_list, 0, 7, 0))
print(test_binary_search("Zidane", FF_list, 0, 7, 7))
print(test_binary_search("Kefka", FF_list, 0, 7, 2))
print(test_binary_search("Vivi", FF_list, 0, 7, 6))
print(test_binary_search("Squall", FF_list, 0, 7, 4))
print(test_binary_search("Zaphod Beeblebrox", FF_list, 0, 7, None))

[essepuntato]

Hi all,

please find attached my personal solution – also available online:

# Test case for the function
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

# Code of the function
def binary_search(item, ordered_list, start, end):
    if start <= end:
        mid = ((end - start) // 2) + start
        mid_item = ordered_list[mid]
        if item == mid_item:
            return mid
        elif mid_item < item:
            return binary_search(item, ordered_list, mid + 1, end)
        else:
            return binary_search(item, ordered_list, start, mid - 1)

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