Hunting for the Target: A Guide to Search Algorithms (Part - 2)
In the previous blogs, we focused on Time and Space complexity concepts, basic sorting algorithms, and Basic searching algorithms. Searching algorithms are methods for finding a specific item or value in a collection of data, such as an array or list. The goal is to find the target item as efficiently as possible, and the efficiency of a search algorithm is measured by the time it takes to find the item, compared to the size of the data set being searched.
This blog is focused on the last set of search algorithms that we would be discussing! This includes:
Interpolation Search
Exponential Search
Fibonacci Search
Ternary Search
Interpolation Search
A search algorithm that works by estimating the position of the target item based on the values of the first and last elements of the data set.
Uses a formula to calculate the estimated position of the target item within the data set.
Compares the value of the item at the estimated position to the target item.
If the estimated item is equal to the target item, the search is successful.
If the estimated item is less than the target item, the search continues in the portion of the data set after the estimated position.
If the estimated item is greater than the target item, the search continues in the portion of the data set before the estimated position.
The process is repeated until either the target item is found or it is determined that the item is not present in the data set.
Has a time complexity of O(log log n), where n is the number of elements in the data set.
More efficient than binary search for data sets where the values of the elements are uniformly distributed.
Less efficient than binary search for data sets where the values of the elements are not uniformly distributed.
Can be less efficient than a linear search for very small data sets or data sets with many duplicates.
Sample Code
def interpolation_search(arr, x):
lo = 0
hi = len(arr) - 1
while lo <= hi and x >= arr[lo] and x <= arr[hi]:
pos = lo + int(((float(hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo])))
if arr[pos] == x:
return pos
elif arr[pos] < x:
lo = pos + 1
else:
hi = pos - 1
return -1
This implementation uses the interpolation formula to estimate the position of the target value and then narrows down the search by adjusting the lo
and hi
indices based on the comparison between the target value and the value at the estimated position. If the target value is found, the function returns its index, and if the target value is not found, the function returns -1.
It is important to note that the interpolation search algorithm works best when the data follows a uniform distribution. If the data has a non-uniform distribution, it may result in a slower search.
Exponential Search
A search algorithm works by first checking the range where the target item is likely to be located.
Begins by checking the value of the item at the first power of two that is greater than or equal to the number of elements in the data set.
If the item at that position is less than the target item, the search continues in the portion of the data set after the current position.
If the item at that position is greater than the target item, a binary search is performed on the portion of the data set before the current position.
The process is repeated until either the target item is found or it is determined that the item is not present in the data set.
Has a time complexity of O(log n), where n is the number of elements in the data set.
More efficient than linear search for large data sets.
Not as efficient as a binary search for data sets where the values of the elements are uniformly distributed.
Can be more efficient than a binary search for data sets where the values of the elements are not uniformly distributed.
Not suitable for very small data sets.
Sample Code
def exponential_search(data, target):
n = len(data)
if data[0] == target:
return 0
i = 1
while i < n and data[i] <= target:
i = i * 2
return binary_search(data, i // 2, min(i, n), target)
def binary_search(data, low, high, target):
while low <= high:
mid = (low + high) // 2
if data[mid] == target:
return mid
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
In this code, data
is the list or array being searched, and target
is the item being searched for. The exponential_search
function first checks the first power of two that is greater than or equal to the number of elements in the data set and returns the result of a binary search on the portion of the data set that is likely to contain the target item. The binary_search
function performs a standard binary search and returns the position of the target item if it is found, or -1
if it is not present in the data set.
Fibonacci Search
A search algorithm that uses Fibonacci numbers to divide a sorted data set into smaller sub-sets.
Begins by finding the closest Fibonacci number to the number of elements in the data set.
Uses the value of the Fibonacci number to determine the size of the sub-sets to be searched.
Searches the sub-set that is likely to contain the target item.
If the target item is not found, the process is repeated on the next sub-set.
Continues until either the target item is found or it is determined that the item is not present in the data set.
Has a time complexity of O(log n), where n is the number of elements in the data set.
Can be more efficient than a binary search for data sets where the values of the elements are not uniformly distributed.
Not as efficient as a binary search for data sets where the values of the elements are uniformly distributed.
Can be less efficient than other search algorithms for very large data sets.
def fibonacci_search(data, target):
n = len(data)
fib_m_2 = 0
fib_m_1 = 1
fib = fib_m_1 + fib_m_2
while fib < n:
fib_m_2 = fib_m_1
fib_m_1 = fib
fib = fib_m_1 + fib_m_2
offset = -1
while fib > 1:
i = min(offset + fib_m_2, n - 1)
if data[i] < target:
fib = fib_m_1
fib_m_1 = fib_m_2
fib_m_2 = fib - fib_m_1
offset = i
elif data[i] > target:
fib = fib_m_2
fib_m_1 = fib_m_1 - fib_m_2
fib_m_2 = fib - fib_m_1
else:
return i
if fib_m_1 and data[offset + 1] == target:
return offset + 1
return -1
In this code, data
is the list or array being searched, and target
is the item being searched for. The fibonacci_search
the function uses the Fibonacci sequence to divide the data set into sub-sets and searches each sub-set until the target item is found or it is determined that the item is not present in the data set. The function returns the position of the target item if it is found, or -1
if it is not present in the data set.
Ternary Search
A search algorithm divides the data set into three equal parts and recursively searches the part that is most likely to contain the target item.
The data set must be sorted in ascending or descending order.
Each iteration of the algorithm narrows the search space by one-third.
Continues until either the target item is found or it is determined that the item is not present in the data set.
Has a time complexity of O(log3 n), where n is the number of elements in the data set.
Can be more efficient than binary search for certain data sets where the values of the elements are not uniformly distributed.
Is less efficient than binary search for most data sets.
Can be less efficient than other search algorithms for very large data sets.
The choice of dividing the data set into three equal parts can be adjusted for better performance on specific data sets.
Ternary search is not as widely used as other search algorithms, such as binary search or linear search.
def ternary_search(data, target):
def ternary_search_helper(data, target, left, right):
if left > right:
return -1
mid1 = left + (right - left) // 3
mid2 = right - (right - left) // 3
if data[mid1] == target:
return mid1
if data[mid2] == target:
return mid2
if target < data[mid1]:
return ternary_search_helper(data, target, left, mid1 -1)
elif target > data[mid2]:
return ternary_search_helper(data, target, mid2 + 1, right)
else:
return ternary_search_helper(data, target, mid1 + 1, mid2 - 1)
return ternary_search_helper(data, target, 0, len(data) - 1)
In this code, data
is the list or array being searched, and target
is the item being searched for. The ternary_search
function uses a recursive helper function, ternary_search_helper
to divide the data set into three equal parts and search for the part that is most likely to contain the target item. The ternary_search_helper
function continues to narrow the search space until the target item is found or it is determined that the item is not present in the data set. The ternary_search
function returns the position of the target item if it is found, or -1
if it is not present in the data set.
Interpolation Search is an efficient search algorithm that uses information about the distribution of values within the data set to more quickly locate the target item. Exponential Search is an efficient search algorithm that incrementally increases the size of the search space, taking advantage of the fact that the target item is likely to be located close to the end of the data set. Fibonacci Search is a search algorithm that uses the Fibonacci sequence to determine the size of the search space, which can improve the time complexity compared to binary search. Ternary Search is a search algorithm that divides the data set into three equal parts and recursively searches the part that is most likely to contain the target item.
Conclusion
In conclusion, interpolation search, exponential search, Fibonacci search, and ternary search are all algorithms that can be used to efficiently search for a target value within a sorted array. Each of these algorithms has its own strengths and weaknesses and the choice of which algorithm to use depends on the specific requirements of the problem being solved.
Interpolation search uses an estimate of the position of the target value to narrow down the search and works best when the data follows a uniform distribution.
Exponential search increases the size of the subarray being searched in each iteration, making it faster than binary search when the target value is closer to the start of the array.
The Fibonacci search uses Fibonacci numbers to determine the size of the subarray being searched and is similar to exponential search but with slower worst-case time complexity.
Ternary search divides the array into three parts in each iteration, making it faster than binary search in the average case but slower in the worst case.
When choosing an algorithm for a search problem, it is important to consider the time complexity, space complexity, and distribution of the data. Based on these factors, the most appropriate algorithm can be selected to solve the problem in an efficient and effective manner.