Binary Search and Insertion Sort

Written By Adebola Oshomoji, Edited By Mae Semakula-Buuza
Sun 12 August 2018, in category Python

python

  
@

Introduction

In this article, I will provide an overview of the binary search and insertion sort algorithms. A Python implementation of these concepts will also be provided to help build understanding.

The contents of this article are based on lessons from Brilliant’s ‘Computer Science Fundamentals’ course that I had previously gone through.

Sorting and Searching

Searching and sorting are examples of tasks that are often regarded as mundane, especially if they are being completed by a human. Whether we are searching for telephone numbers or sorting out money in our head, we tend to do this without much thought. However, a lot more thought needs to be go into it when programming computers to complete these tasks for us. Before we go into greater detail on the specifics of various search or sort algorithms, it’ll be worth going over some definitions for these two concepts.

Search

Search is the process of finding a specific (target) value within a collection of values. At its simplest, each element within the collection is looked at in turn until we find an item that matches our target. If all elements are exhausted without finding our target value, we conclude that the collection does not contain our target.

Sort

Sorting is the process of bringing order to an unordered collection of items. Comparisons are made between each element of the collection until an order is established based on size differences. The rule for determining the sizes is established before sorting commences. For example, if we were working with a collection of words, and needed to sort these elements alphabetically, sizes would be based on each letter’s position within the alphabet. After determining an order, the elements of the collections are rearranged.

Examples of search and sort algorithms include: linear search, binary search, jump search, insertion sort, merge sort, and bubble sort. This blog post will primarily focus on binary search and insertion sort algorithms. A minor comparison will be also be made between linear search and binary search.

If you are interested in learning more about the search and sort algorithms not covered in this article, as well as their pros and cons, visit the links below:

https://www.geeksforgeeks.org/searching-algorithms/

https://www.geeksforgeeks.org/sorting-algorithms/

Binary Search

Now that we know the definition for ‘search’, let’s explore one simple approach of searching for a target value within a collection of items. To recap, one could simply go through each of the elements within the collection to try to find our target - this approach is called linear search.

While linear search is a viable option when working with a small number of items, it quickly becomes unfeasible as our collection size starts to scale. To help conceptualise this, let’s think about viability of searching for a specific telephone number in the yellow pages by going through each of the records in order. Not very practical, is it? Therefore, an alternative approach is preferable when working with larger data sizes.

Binary search implementation

Figure 1. An example of a binary search implementation

An example of a more preferable search algorithm is binary search. To avoid blindly searching through every element for our target value, binary search halves the portion of our collection that the target value could possibly be found in after every iteration. This portion represents the search space. Figure 1 shows an example of binary search being used to find a number within an array of numbers.

For binary search to occur, our collection (or array) would first need to be sorted. The middle element of our array is then inspected to determine if its value matches that of the target we are trying to find. If the value of this middle element is found to have a smaller value than that of our target, and assuming our array is arranged in ascending order, it is concluded that our target value could only feasibly be present in the portion of the array to the right of the previously inspected (middle) element.

Conversely, if the middle element is found to have a larger value than that of our target, the algorithm reaches the conclusion that our target value could only possibly be found in the portion of the array to the left of the previously inspected element. This process is then repeated with successively smaller portions of the array until the search algorithm either finds our value or concludes that it doesn’t exist.

Equation 1 shows the formula used to find the middle element. Equation 1

Python Implementation of Binary Search

A recursive approach to implementing binary search within Python can be seen below. The value of the calculated middle element is inspected after each step to determine if it equates to the value that we are trying to find. If the values aren’t equal, the binary_search function is called again on a smaller portion of the array. I have included a range of targets to test the code on. This includes values that fall outside the range contained within the array.

def binary_search(array, target, first_index=None, last_index=None):
    """
    Return boolean result indicating presence of target within array

    Function recursively searches for target within array using binary search
    algorithm
    """
    if first_index is None:
        first_index = 0
        last_index = len(array) - 1

    mid_point_index = int((first_index + last_index) / 2)

    if mid_point_index == first_index:
        return array[first_index] == target
    else:
        mid_point = array[mid_point_index]
        if mid_point == target:
            return True
        elif mid_point < target:
            first_index = mid_point_index + 1
            return binary_search(array=array, target=target,
                                first_index=first_index,
                                last_index=last_index)
        elif mid_point > target:
            last_index = mid_point_index - 1
            return binary_search(array=array, target=target,
                                first_index=first_index,
                                last_index=last_index)


if __name__ == '__main__':
    array = [1, 2, 3, 4, 5, 7, 8, 9, 11, 14, 16, 20]
    targets = [9, 8, 6, 13, -2, 20, 14, 1]
    print(array)
    for target in targets:
        result = binary_search(array, target)
        print('{} is in array: {}'.format(target, result))

Insertion Sort

Insertion sort is an example of a simple sorting algorithm. A final sorted array is created by iteratively repositioning each element based on the values to their immediate left. Starting from the leftmost position, each element is shifted left until there are either:

  1. No more values to the left of it or
  2. The element to its immediate left has a smaller or equal value (if sorted in ascending order).

Thinking about it now, insertion sort works similarly to how one would sort their hand in a card game, don’t you think? An example of its implementation for an unsorted array can be seen in Figure 2.

Insertion sort implementation

Figure 2. An example of an insertion sort implementation

Insertion sort works well when sorting small arrays, where only a small amount of comparisons need to be made. It also works well if the array is largely pre-sorted. When this is not the case, other sorting algorithms such as, quicksort is preferable.

Python Implementation of Insertion Sort

A Python implementation of insertion sort can be seen below; this particular implementation uses a number of unsorted arrays to demonstrate the concept.

def insertion_sort(array):
    """
    Return sorted array using insertion sort algorithm

    Each element is compared to values of previous elements to identify
    correct position for insertion.
    """
    for i in range(1, len(array)):
        current_index = i
        previous_index = i - 1
        current_value = array[current_index]
        while (current_value < array[previous_index] and 
            current_index > 0):
            array[current_index] = array[previous_index]
            current_index -= 1
            previous_index -= 1
        array[current_index] = current_value
        print('Iteration {0}: {1}'.format(i, array))


if __name__ == '__main__':
    arrays = [
        [3, 4, 2, 5, 6, 1],
        [6, 5, 4, 3, 2, 1],
        [4, 2, 1, 3, 4, 5],
        [3, 4, 29, 0.5, -2]
    ]
    for array in arrays:
        print('\nUnsorted array: {}'.format(array))
        insertion_sort(array)

Things to note about the code:

Conclusion

I hope this article helped you develop an intuition for these key concepts: binary search and insertion sort. If you are interested in exploring these topics further, Wikipedia provides detailed articles for binary search and insertion sort. These include variations on the algorithms, technical explanations, and code implementations for various languages. Alternatively, Brilliant’s ‘Computer Science Fundamentals’ course is a great resource, not only for binary search and insertion sort, but for learning various topics in a fun and interactive way.