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
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
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!") break elif values[middle] < key: start = middle + 1 else: end = middle - 1 middle = (start + end)//2 else: # means there is nothing left to be searched in print ("Not found!")
key is what we are asking Binary Search to look in
end are the indices that show which part of the array is our Region of Interest, if you will.