The Searching algorithms are essential techniques used to locate an element or value within a dataset. In this article, we’ll delve into several commonly used searching algorithms in Python: Linear Search, Binary Search, Interpolation Search and Jump Search.
1. Linear Search
The Linear search is the most straightforward searching algorithm. It checks each element in the list sequentially until it finds the target value.Steps:
- Start from the first element of the list.
- Compare each element with the target value.
- If a match is found, return its index.
- If no match is found by the end of the list, return -1.
Implementation in 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, value in enumerate(arr):
if value == 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")
Output :
Linear Search: Element found at index 3
2. Binary Search
The Binary search is a more efficient algorithm 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 matches the target, return its index.
- If the middle element is less than the target, search in the right half of the list.
- If the middle element is greater than the target, search in the left half of the list.
- Repeat until the target is found or the interval is empty.
Implementation in 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)
return -1
# Example usage:
arr = [2, 3, 4, 10, 40]
target = 10
result = binary_search(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")
Output :
Binary Search: Element found at index 3
3. Interpolation Search
The Interpolation search is an improvement over binary search for uniformly distributed arrays. It estimates the position of the target value based on the value of the key and the range of the search space.Steps:
- Estimate the position of the target value using interpolation.
- Compare the target value with the element at the estimated position.
- If a match is found, return its index.
- If the element is less than the target, search in the right half.
- If the element is greater, search in the left half.
- Repeat until the target is found or the interval is empty.
Implementation in Python:
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, high = 0, len(arr) - 1
while low <= high and target >= arr[low] and target <= arr[high]:
if low == high:
if arr[low] == target:
return low
return -1
pos = low + ((high - low) * (target - arr[low]) // (arr[high] - 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(arr, target)
if result != -1:
print(f"Interpolation Search: Element found at index {result}")
else:
print("Interpolation Search: Element not found")
Output :
Interpolation Search: Element found at index 3
4. Jump Search
The Jump search is suitable for sorted arrays. It jumps ahead by fixed steps and then performs a linear search within the smaller range.Steps:
- Determine the block size for jumping ahead.
- Jump ahead by the block size until the target is greater than the current block's last element.
- Perform a linear search within the block.
- If the target is found, return its index.
- If not found after all jumps, return -1.
Implementation in 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 prev < n and arr[min(step, n) - 1] < target:
prev = step
step += int(math.sqrt(n))
if prev >= n:
return -1
for i in range(prev, min(step, n)):
if arr[i] == target:
return i
return -1
# Example usage:
arr = [2, 3, 4, 10, 40]
target = 10
result = jump_search(arr, target)
if result != -1:
print(f"Jump Search: Element found at index {result}")
else:
print("Jump Search: Element not found")
Output :
Jump Search: Element found at index 3
Post a Comment