Binary Search:

date posted: 2020-01-11

Binary Search

Binary search is very straight forward, it only works when list is sorted. I will quickly explain its working steps with an example:

1. your search value = 23. In a given list, go to its middle element which is 16. If search value is greater than middle element, take upper part of the list(after 16 until the end).
2. Again compare search value with middle element from upper part we've just taken and repeat step 1.
3. If only 2 element left, choose first element, in this case 23 as your midpoint. Compare it and since it is what we are looking for, we are done.

So main goal of binary search is finding the midpoint.

there are few different ways of choosing a midpoint

1. (lowest_index + highest_index)/2 and round it down
2. lowest_index + (highest_index - lowest_index)/2

so using the first method in our case of 10-element list. first midpoint would be 0 + 9/2 = 4.5, rounded down to 4. and 4 means index, 4th element which is 16.

Python implementation

    import math
    def binarySearch(lst, key):
        low = 0
        end = len(lst) -1
        
        while low <= end:
            mid = math.floor((low + end)/2)
            
            if key == lst[mid]:
                return f'key {key} = lst[{mid}]'
            
            elif key < lst[mid]:
                end = mid - 1
            else:
                low = mid + 1
        return f'{key} is not in this list'
    

Time complexity

When given ordered list and perform binary search Time complexity is O(n) = log(n)

but what if list is not ordered?

In such case we would need to add time complexity of sorting algorithm + time complexity of binary search

Depending on the use case you would need to use linear search or binary search.

ex: if you have unsorted list with million elements and you are only going to search once in this case you would just use linear search. Using linear search will give O(n) = n, however using sorting then binary search would give O(n log n) + O(log n) = O(n log n).

BUT if you need to keep on using search algorithm on that list, it would be much better to sort once, then keep on using binary search since as search frequency increase using binary search will make up for its sorting algorithm in the beginning.

1. for sorting a list once then keep on applying binary search: O(n log n) + (number_of_search) O(log n).
2. for linear search: (number_of_search) O(n).

let number_of_search = 100
len(list) = 10
note: log10 = 3.321928... (log base 2)
so using 1st method, 10 log(10) + 100(log(10)) = 365.41208
using 2nd methos, 100(10) = 1000.

We can clearly see even for 100 search sorting a list once then applying binary search would be much more efficient way. So if you are going to search multiple times, you would use method 1. If only few times, use method 2.