Hunting for the Target: A Guide to Search Algorithms (Part - 1)
In the previous blogs, we focused on Time and Space complexity concepts followed by basic sorting algorithms, Next in the series we have 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.
There are several types of search algorithms, including linear search, binary search, and jump search. Each algorithm uses a different approach, but the basic idea is to narrow down the search space until the target item is found or it can be determined that the item is not in the data set.
In this blog, we will be focusing on 3 of the most basic algorithms: Linear Search, Binary Search, and Jump Search.
The upcoming blog will continue the exploration of the search domain and the focus would shift to Interpolation Search, Exponential search, Fibonacci search, and Ternary Search.
Linear Search
Simple search algorithm.
Involves checking each element in the data set one by one.
Begins at the first element and compares it to the target item.
If the first element is the target item, the search is successful.
If not, the algorithm moves on to the next element and repeats the comparison process.
The process continues until either the target item is found or all elements have been checked and it is determined that the target item is not present in the data set.
Has a best-case time complexity of O(1) and a worst-case time complexity of O(n), where n is the number of elements in the data set.
Suitable for small data sets or when the data is unordered.
Can be slow for large data sets.
Sample Code
def linear_search(data, target):
for i in range(len(data)):
if data[i] == target:
return i
return -1
Binary Search
A more efficient search algorithm compared to linear search, especially for large data sets.
Works by repeatedly dividing the data set in half, discarding half of the data set each time.
Begins by comparing the middle element to the target item.
If the middle element is equal to the target item, the search is successful.
If the middle element is less than the target item, the search continues in half of the data set that contains elements greater than the middle element.
If the middle element is greater than the target item, the search continues in half of the data set that contains elements less than the middle element.
This 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 best-case and worst-case time complexity of O(log n), where n is the number of elements in the data set.
Requires that the data set is sorted.
More efficient for large data sets.
Sample Code
def binary_search(data, target):
low = 0
high = len(data) - 1
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
The low
and high
variables keep track of the boundaries of the portion of the data set that is being considered in each iteration of the loop. The mid
variable calculates the index of the middle element in the current portion of the data set.
The loop continues until either the target item is found (in which case its index is returned), or it is determined that the item is not present in the data set (in which case -1
is returned). At each iteration, the portion of the data set being considered is halved by updating the low
or high
variable, and the comparison is made with the middle element of the current portion.
Jump Search
The search algorithm works by dividing the data set into blocks and checking only one element in each block.
The size of each block is determined by the square root of the number of elements in the data set.
Begins by comparing the first element in the first block to the target item.
If the first element is equal to the target item, the search is successful.
If the first element is less than the target item, the search continues in the next block.
If the first element is greater than the target item, a linear search is performed within the current block to find the target item.
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(√n), where n is the number of elements in the data set.
More efficient than a linear search for data sets that are too large for a linear search but too small for a binary search.
The efficiency of the jump search can be improved by adjusting the size of the blocks, but this can make the algorithm more complex.
Sample Code
import math
def jump_search(data, target):
n = len(data)
step = int(math.sqrt(n))
prev = 0
while data[min(step, n) - 1] < target:
prev = step
step += int(math.sqrt(n))
if prev >= n:
return -1
while data[prev] < target:
prev += 1
if prev == min(step, n):
return -1
if data[prev] == target:
return prev
return -1
The step
variable determines the size of each block and is initially set to the square root of the number of elements in the data set. The prev
variable keeps track of the position in the data set where the previous block ended.
The first loop jumps from one block to the next, until a block is found where the first element is greater than or equal to the target item. The second loop performs a linear search within the current block to find the target item. If the target item is not found in either loop, -1
is returned to indicate that the item is not present in the data set.
Conclusion
In conclusion, searching algorithms are an essential part of computer science and play a crucial role in optimizing the time and space complexity of finding a target item within a data set. There are several search algorithms, each with its own strengths and weaknesses, and the choice of which algorithm to use depends on the specific requirements of the task at hand.
Linear Search is a simple search algorithm that iterates through each element of the data set and returns the position of the target item if it is found.
Binary Search is an efficient search algorithm that divides the data set into two equal parts and recursively searches for the part that is most likely to contain the target item.
Jump Search is an efficient search algorithm that jumps through the data set in fixed-size steps, which can improve the time complexity compared to linear search.