Divide and Conquer Algorithms: Binary Search & Visualizing it’s Time Complexity
Consider an array of sorted numbers, with n elements. The simplest searching algorithm available is the linear sort. In this algorithm, we start from the leftmost element and compare it with the search term; if the search term matches the number on the index we are currently on, then the search operation is successful and the index is returned, but, if the numbers don’t match, then we go to the number on the next index and follow the same procedure till the number is found. If the number isn’t present, we return that the search was unsuccessful. The time complexity of linear sort is O(n). This may hence take enormous time when there are many inputs.
This is when we need a divide and conquer strategy to reduce the time taken by the search procedure. Binary search is one such divide and conquer algorithm to assist with the given problem; note that a sorted array should be used in this case too. This search algorithm recursively divides the array into two sub-arrays that may contain the search term. It discards one of the sub-array by utilising the fact that items are sorted. It continues halving the sub-arrays until it finds the search term or it narrows down the list to a single item. Since binary search discards the sub-array it’s pseudo Divide & Conquer algorithm. What makes binary search efficient is the fact that if it doesn’t find the search term in each iteration, it just reduces the array/list to it’s half for the next iteration. The time complexity of binary search is O(log n), where n is the number of elements in an array. If the search term is at the centre of the array, it’s considered to be the best case since the element is found instantly in a go. Hence the best case complexity will be O(1).
Now, consider the above-mentioned time complexities. Complexities like O(1) and O(n)are very intuitive to understand:
1. O(1) : refers to an operation where the value/the element is accessed directly
2. O(n) : refers to a (set of) where the element can only be accessed by traversing a set of n elements, like in linear search.
But what does O(log n) really mean? It may seem difficult to understand but let’s visualize it using a simple example of binary search, while searching for a number in a sorted array which will take the worst-case time complexity:
- n = 16 (no. of elements in the sorted array)
2. The middle element is selected as the pivot
3. Since the array is already sorted, and 13 is less than the pivot element, the other half of the array is redundant and hence removed.
4. The procedure for finding the pivot (middle) element for every sub-array is repeated.
5. The searching range is halved after every comparison with the pivot element.
6. The array was divided 4 times to reach the required value in an array of 16 elements. Therefore,
Therefore, for n number of elements:
Multiplying both sides by 2^k
Result:
Converting the result to its logarithmic form:
We have successfully visualized O(log n) time complexity!
Images used here rightfully belong to the following Hacker Noon user.
