ECX 30 Days of Code and Design

Day 25

Binary Search Algorithm

Task

Binary search is a basic algorithm used to find the position of a target value within a sorted list. For today's task, write a function that takes in two parameters: a list of alphabets, and a character to search for. E.g.; f(['m', 'v', 'x', 'u'], “x”)

In your function:

1. First, check if the input list is sorted using any method of your preference. If it is unsorted, return a warning indicating so, else continue
2. Using the binary search algorithm, find the position of the input character in the sorted list
3. Return the position of the character in the search list
4. If the character is not found, return false More details can be found here: Binary search

My Approach

Below is the full code. I will explain it in bits throughout this article.

def binary_search(list_item, search_item):
    """Finds the index of a letter from a list using binary search algorithm."""
    list_item_sorted = list_item[:]
    list_item_sorted.sort()

    # Check if the list is sorted
    if list_item == list_item_sorted:
        left_index = 0
        right_index = len(list_item) - 1

        while left_index <= right_index:
            middle_index = int((left_index + right_index) / 2)

            if list_item[middle_index] < search_item:
                left_index = middle_index + 1

            elif list_item[middle_index] > search_item:
                right_index = middle_index - 1

            else:
                return print(search_item + ' index: ' + str(middle_index))

        print(search_item, 'is not in the list.')

    else:
        print('The list is not ordered.')


list_items = ['a', 'b', 'c', 'd', 'f', 'g', 'y', 'z']

# Function calls
binary_search(list_items, 'b')
binary_search(list_items, 'y')
binary_search(list_items, 'h')

First, we define the function, binary_search(), which would be used to find a letter from a list using the binary search algorithm. Next, we copy list_item to list_item_sorted which we would sort. Notice that we used list_item_sorted = list_item[:] and not list_item_sorted = list_item, because the latter though would copy the other list, would also cause list_item_sorted to reference list_item; that is, when we sort list_item_sorted, list_item would also be sorted.

def binary_search(list_item, search_item):
    """Finds the index of a letter from a list using binary search algorithm."""
    list_item_sorted = list_item[:]
    list_item_sorted.sort()

Next, we check if list_item is sorted by comparing it with list_item_sorted. If it is not sorted, we print “The list is not ordered” on the screen.

    if list_item == list_item_sorted:
  --snip--
    else:
        print('The list is not ordered.')

We create two variables, left_index and right_index which we would use to check for the character in the list.

    if list_item == list_item_sorted:
        left_index = 0
        right_index = len(list_item) - 1

Next, using while loop, whilst left_index is less than or equal to the right_index, we create a variable, middle_index, having a value which is equal to the floor value of half the value of the addition of the values of left_index and right_index. If the item in the middle of the list is less than the ASCII value of the character we are looking for in the list, we make left_index = middle_index + 1; that is, the first to the middle values on the list are all less than the value we are looking for, thus we can make left_index start from the value after the middle value. If the middle value is more than the ASCII value of the search item, we make right_index = middle_index – 1; that is, all the values from the middle value to that last value are greater than the ASCII value of the character we are searching for; therefore, we would make the value of right_index one less than the value of the middle value. The while loop continues until middle_index value equals search_item value. If the character is not in the list, we print on the screen that it is not in the list.

        while left_index <= right_index:
            middle_index = int((left_index + right_index) / 2)

            if list_item[middle_index] < search_item:
                left_index = middle_index + 1

            elif list_item[middle_index] > search_item:
                right_index = middle_index - 1

            else:
                return print(search_item + ' index: ' + str(middle_index))

        print(search_item, 'is not in the list.')

Next, we create a list of characters and pass it into the functions as arguments to test for cases where the character to be searched is less than the middle value, more than the middle value, and not in the list.

list_items = ['a', 'b', 'c', 'd', 'f', 'g', 'y', 'z']

binary_search(list_items, 'b')
binary_search(list_items, 'y')
binary_search(list_items, 'h')

Output

b index: 1
y index: 6
h is not in the list.

Run code on Replit.