Searching Algorithms in Python
Last Updated :
01 Jun, 2024
Searching algorithms are fundamental techniques used to find an element or a value within a collection of data. In this tutorial, we’ll explore some of the most commonly used searching algorithms in Python. These algorithms include Linear Search, Binary Search, Interpolation Search, and Jump Search.
1. Linear Search
Linear search is the simplest searching algorithm. It sequentially checks each element of the list until it finds the target value.
Steps:
- Start from the first element of the list.
- Compare each element of the list with the target value.
- If the element matches the target value, return its index.
- If the target value is not found after iterating through the entire list, return -1.
Implementation of Linear Search in Python:
Python
def linear_search(arr, target):
"""
Perform linear search to find the target value in the given list.
Parameters:
arr (list): The list to be searched.
target: The value to be searched for.
Returns:
int: The index of the target value if found, otherwise -1.
"""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
# Example usage:
arr = [2, 3, 4, 10, 40]
target = 10
result = linear_search(arr, target)
if result != -1:
print(f"Linear Search: Element found at index {result}")
else:
print("Linear Search: Element not found")
OutputLinear Search: Element found at index 3
2. Binary Search
Binary search is a more efficient searching algorithm suitable for sorted lists. It repeatedly divides the search interval in half until the target value is found.
Steps:
- Start with the entire sorted list.
- Compute the middle element of the list.
- If the middle element is equal to the target value, return its index.
- If the middle element is less than the target value, search in the right half of the list.
- If the middle element is greater than the target value, search in the left half of the list.
- Repeat steps 2-5 until the target value is found or the search interval is empty.
Implementation of Binary Search in Python (Recursive):
Python
def binary_search(arr, target, low, high):
"""
Perform binary search recursively to find the target value in the given sorted list.
Parameters:
arr (list): The sorted list to be searched.
target: The value to be searched for.
low (int): The lower index of the search interval.
high (int): The upper index of the search interval.
Returns:
int: The index of the target value if found, otherwise -1.
"""
if low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search(arr, target, mid + 1, high)
else:
return binary_search(arr, target, low, mid - 1)
else:
return -1
# Example usage:
arr = [2, 3, 4, 10, 40]
target = 10
result = binary_search(sorted(arr), target, 0, len(arr) - 1)
if result != -1:
print(f"Binary Search: Element found at index {result}")
else:
print("Binary Search: Element not found")
OutputBinary Search: Element found at index 3
3. Interpolation Search
Interpolation search is an improved version of binary search, especially suitable for large and uniformly distributed arrays. It calculates the probable position of the target value based on the value of the key and the range of the search space.
Steps:
- Calculate the probable position of the target value using interpolation formula.
- Compare the target value with the element at the calculated position.
- If the element matches the target value, return its index.
- If the element is less than the target value, search in the right half of the list.
- If the element is greater than the target value, search in the left half of the list.
- Repeat steps 1-5 until the target value is found or the search interval is empty.
Implementation of Interpolation Search in Python:
Python
import math
def interpolation_search(arr, target):
"""
Perform interpolation search to find the target value in the given sorted list.
Parameters:
arr (list): The sorted list to be searched.
target: The value to be searched for.
Returns:
int: The index of the target value if found, otherwise -1.
"""
low = 0
high = len(arr) - 1
while low <= high and target >= arr[low] and target <= arr[high]:
pos = low + ((high - low) // (arr[high] - arr[low])) * (target - arr[low])
if arr[pos] == target:
return pos
elif arr[pos] < target:
low = pos + 1
else:
high = pos - 1
return -1
# Example usage:
arr = [2, 3, 4, 10, 40]
target = 10
result = interpolation_search(sorted(arr), target)
if result != -1:
print(f"Interpolation Search: Element found at index {result}")
else:
print("Interpolation Search: Element not found")
OutputInterpolation Search: Element found at index 3
4. Jump Search
Jump search is another searching algorithm suitable for sorted arrays. It jumps ahead by a fixed number of steps and then performs a linear search in the smaller range.
Steps:
- Determine the block size to jump ahead.
- Jump ahead by block size until the target value is greater than the current block’s last element.
- Perform linear search within the current block to find the target value.
- If the target value is found, return its index.
- If the target value is not found after iterating through all blocks, return -1.
Implementation of Jump Search in Python:
Python
import math
def jump_search(arr, target):
"""
Perform jump search to find the target value in the given sorted list.
Parameters:
arr (list): The sorted list to be searched.
target: The value to be searched for.
Returns:
int: The index of the target value if found, otherwise -1.
"""
n = len(arr)
step = int(math.sqrt(n))
prev = 0
while arr[min(step, n) - 1] < target:
prev = step
step += int(math.sqrt(n))
if prev >= n:
return -1
while arr[prev] < target:
prev += 1
if prev == min(step, n):
return -1
if arr[prev] == target:
return prev
return -1
# Example usage:
arr = [2, 3, 4, 10, 40]
target = 10
result = jump_search(sorted(arr), target)
if result != -1:
print(f"Jump Search: Element found at index {result}")
else:
print("Jump Search: Element not found")
OutputJump Search: Element found at index 3
Conclusion
In this tutorial, we’ve covered four fundamental searching algorithms in Python: Linear Search, Binary Search, Interpolation Search, and Jump Search. Each algorithm has its advantages and is suitable for different scenarios. Understanding these algorithms and their implementations will help you effectively search for elements within a collection of data.
Please Login to comment...