Posts /

Algo #2: Binary Search with Insertion Sort

4 mins read ●
Twitter Facebook Google+
01 Sep 2017

Binary Search

In the world of technology and Internet, searching is everywhere. Either you are searching a query on Google or looking for a friend on Facebook, searching is your friend. In order to make this search robust, website and software development companies tend to look for algorithms that can search for something fast.
Binary Search is an important algorithm in this regard. But it is not practically used, as there have been developed much better solutions. Still, it is a good to understand it if one is new to algorithms. Dive into more theoretical details here.


Binary Search is used on Array (or List in Python) data structure. It has average time complexity of O(log n). Hence, it is better choice over Linear Search which has O(n).


For it to work correctly, Binary Search needs the data to be sorted. Sorting the data, like searching, is an important problem, but I’ll get back to it later. For now, I’ll be using the simplest of sorting algorithms, Insertion Sort.



The first code snippet contains function to sort the data. Insertion Sort is used in this function.

def sort( values ):
    n = len(values) # size of list
    for i in range(n - 1):
        for j in range(n - i - 1):
    	```move the smallest digit to the front, one step at a time```
            if values[j] > values[j + 1]:
                # swapping
                temp = values[j]
                values[j] = values[j + 1]
                values[j + 1] = temp
    return values
Insertion Sort Animation  
Visual representation of Insertion Sort.


Once the data is sorted, binary search algorithm starts searching for the required data. The reason for it being faster than Linear Search is that in each step it discards the half of the data present at that time. It does so by comparing the required data to the middle of sorted data list. As the data is sorted, the algorithm knows which part of the list is likely to contain the data of interest, so it discards the other half. This goes on and on until the concern element is found or all the data is discarded i.e., search query not found.

def search( values, key ):
    values = sort(values) # sorted array to be fed into binary search
    n = len(values) # size
    start = 0
    end  = n - 1
    middle = (start + end)//2
    while start <= end:
        if values[middle] is key:
            print ("Found!")
        elif values[middle] < key:
            start = middle + 1
            end = middle - 1
        middle = (start + end)//2
    else: # means there is nothing left to be searched in
        print ("Not found!")

Here, key is what we are asking Binary Search to look in values. start and end are the indices that show which part of the array is our Region of Interest, if you will.

Binary Search Animation  
Visual representation of Binary Search.

See the result in this IPython Notebook. In case of any errors, open an issue in 100 Algorithms repo.

You may also like...

Twitter Facebook Google+