Searching Algorithms

Algorithms are step-by-step procedures or instructions to solve problems efficiently. In Python, implementing algorithms is much easier due to its simple syntax and powerful libraries. Algorithms can be broadly categorized into searching, sorting, and optimization techniques, among others.

Searching Algorithms

Searching Algorithms are techniques used to find the position or existence of a specific element within a collection of data such as an array, list, or database. They help in efficiently locating data without checking every element manually. Common searching algorithms include Linear Search and Binary Search, each with different performance and use cases.

Linear Search Algorithm

Linear Search is the simplest searching technique where each element in a dataset is checked one by one until the target element is found. It works well on unsorted data, but can be inefficient for large datasets because it may need to examine every element. Its time complexity is O(n), where n is the number of elements.

In Python, linear search can be implemented using loops. The main operations performed in linear search are:

• Search: Check each element sequentially to find the target.
• Comparison: Compare the current element with the target.
• Return: Stop and return the position/index once the target is found; otherwise, indicate it is not present.

Linear search is widely used in small datasets, unsorted collections, or when simplicity is preferred over efficiency.

Example

Input:

arr = [10, 25, 30, 45, 50]
x = 30

for i in range(len(arr)):
    if arr[i] == x:
        print("Element found at index:", i)
        break

Output:

Element found at index: 2

Binary Search Algorithm

Binary Search is a more efficient searching technique that works on sorted arrays. It repeatedly divides the search space in half, comparing the target value with the middle element to determine whether to search the left or right half. This reduces the time complexity to O(log n), making it much faster than linear search for large datasets.

In Python, binary search can be implemented using loops or recursion. The main operations performed in binary search are:

• Divide: Find the middle element of the current search space.
• Compare: Check if the middle element matches the target.
• Search: If the target is smaller, continue in the left half; if larger, continue in the right half.
• Return: Stop and return the position once the target is found; otherwise, indicate it is not present.

Binary search is widely used in database lookups, dictionary searches, search engines, and any application involving large sorted datasets.

Example :

Input:

arr = [10, 20, 30, 40, 50]
x = 30
low, high = 0, len(arr) - 1

while low <= high:
    mid = (low + high) // 2
    if arr[mid] == x:
        print("Element found at index:", mid)
        break
    elif arr[mid] < x:
        low = mid + 1
    else:
        high = mid - 1

Output:

Element found at index: 2

Graphical Representation of Linear Search Algorithm

Binary Search Algorithm

Binary Search is a more efficient searching technique that works on sorted arrays. It repeatedly divides the search space in half, comparing the target value with the middle element to determine whether to search the left or right half. This reduces the time complexity to O(log n), making it much faster than linear search for large datasets.

In Python, binary search can be implemented using loops or recursion. The main operations performed in binary search are:

• Divide: Find the middle element of the current search space.
• Compare: Check if the middle element matches the target.
• Search: If the target is smaller, continue in the left half; if larger, continue in the right half.
• Return: Stop and return the position once the target is found; otherwise, indicate it is not present.

Binary search is widely used in database lookups, dictionary searches, search engines, and any application involving large sorted datasets.

Example :

Input:

arr = [10, 20, 30, 40, 50]
x = 30
low, high = 0, len(arr) - 1

while low <= high:
    mid = (low + high) // 2
    if arr[mid] == x:
        print("Element found at index:", mid)
        break
    elif arr[mid] < x:
        low = mid + 1
    else:
        high = mid - 1

Output:

Element found at index: 2