--
The easiest search algorithm is Linear Search, and it is pretty intuitive. It is exactly like how a child tries to find an element. You loop over the array until you find the item you are looking for. It is so easy to implement, but imagine that we have an array of 1,000,000 items. This algorithm will be too inefficient. Its run complexity is O(n), which is not great. That is why we need other search algorithms.
This algorithm is similar to the Linear Search algorithm, but it has some adjustments. It divides the array into several blocks. Each block has the size of √n. Then we check if the last item is less than the target or not. If it is greater, we search this block linearly. To be honest, The Binary Search algorithm, which we will discuss, is much better in performance, but a good software engineer must know all the algorithms that are available out there.
The Binary Search algorithm is arguably the best, but it requires your array to be sorted. It simply works by getting the middle index and comparing it with your target. If the target is greater than the middle, it will ignore the left part and search the right part. Remember the array is sorted. It will repeat this process until finding the target. The special thing about binary search is that it runs in O(log(n)). It’s the best algorithm in terms of efficiency until now at least.
Do you remember the one-million-item array? if you used this algorithm to search for an item, you would find it in just 19 steps! That is why we consider it the best.
Binary Search can be implemented recursively and iterable, The recursive method requires a space complexity of O(log(n)) , as it will store the recursive calls on the heap. However, this is negligible as it’s not memory-consuming to store this tiny space. Moreover, the recursive call implementation is cleaner. The iterable method requires a space complexity of O(1). That’s why some see that it’s a better implementation. Yet, both ways are fine.
Ternary Search is another algorithm that is similar to Binary Search. It works by dividing the array into three parts instead of two and checking some five conditions instead of three. By dividing the array into 3 parts, we get 2 middle items. First, we will check if any of those 2 middle items equals the target. If not, we will determine which part of the array the target is in and recursively search it.
Here is its implementation in Python if you like to understand the code more than human words.
def ternary_search(array, target):
left = 0
right = len(array) - 1 def ternary_search_implementation(array, target, left, right):
# Check if the array is empty
if left > right:
return -1
partition_size = round((right - left) / 3)
mid1 = left + partition_size
mid2 = right - partition_size
if array[mid1] == target:
return mid1
if array[mid2] == target:
return mid2
# Check if the target is in the middle part
if array[mid1] < target and array[mid2] > target:
return ternary_search_implementation(array, target, mid1 + 1, mid2 - 1)
# Check if the target is in the right part
if array[mid2] < target:
return ternary_search_implementation(array, target, mid2 + 1, right)
# Check if the target is in the left part
if array[mid1] > target:
return ternary_search_implementation(array, target, left, mid1 - 1)
return ternary_search_implementation(array, target, left, right)
The Exponential Search uses the Binary Search algorithm but in a different way. It starts with an element of the array and compares it with the target. If the target is greater, it doubles the number of elements taken from the array. Typically this number is called bound. If the bound is greater than the target, we search the array from bound /2 to bound. In this search, we use binary search. This algorithm runs inO(log(i)) not O(log(n)) because we only search from the bound to its half.
