Search algorithms are fundamental in computer science and are used to find specific elements within a data structure. Whether it’s searching for a word in a document, locating a product in an online store, or finding a route on Google Maps, search algorithms play a crucial role. In this blog, we’ll explore how search algorithms work, focusing on two main types: linear search and binary search, with Python examples.

1. Linear Search

Linear search is the simplest search algorithm. It checks each element in a list sequentially until it finds the target value or reaches the end of the list.

How It Works:

• Start from the first element and compare it with the target.
• If a match is found, return the index.
• If no match is found, return -1 or a message indicating the element is not present.

Python Implementation:

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return the index where the element is found
    return -1  # Element not found

# Example 
numbers = [10, 25, 36, 48, 59, 72]
target = 36
result = linear_search(numbers, target)
print(f"Element found at index: {result}" if result != -1 else "Element not found")

Time Complexity:

• Best Case: O(1) (if the element is the first in the list)
• Worst Case: O(n) (if the element is at the end or not present)

Linear search is useful for unsorted lists or when the dataset is small.

2. Binary Search

Binary search is much faster than linear search but requires the list to be sorted. It works by repeatedly dividing the search space in half until the target is found.

How It Works:

1. Find the middle element of the sorted list.
2. If the middle element matches the target, return its index.
3. If the target is smaller than the middle element, search the left half.
4. If the target is larger, search the right half.
5. Repeat until the element is found or the list is empty.

Python Implementation:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2  # Find the middle index
        if arr[mid] == target:
            return mid  # Element found
        elif arr[mid] < target:
            left = mid + 1  # Search in the right half
        else:
            right = mid - 1  # Search in the left half
    return -1  # Element not found

# Example 
sorted_numbers = [5, 12, 18, 24, 36, 42, 55]
target = 24
result = binary_search(sorted_numbers, target)
print(f"Element found at index: {result}" if result != -1 else "Element not found")

Time Complexity:

• Best Case: O(1) (if the middle element is the target)
• Worst Case: O(log n) (reduces the search space by half in each step)

Binary search is efficient for large datasets but requires sorting first, making it ideal for static data.

Comparison of Linear Search vs. Binary Search

Feature	Linear Search	Binary Search
List Requirement	Unsorted or sorted	Must be sorted
Time Complexity (Worst Case)	O(n)	O(log n)
Best for	Small datasets	Large datasets
Ease of Implementation	Easy	Requires sorting first

Conclusion

Search algorithms are essential in data handling and retrieval. While linear search is simple and works on unsorted data, binary search is much faster but requires sorting. Choosing the right search algorithm depends on the nature of the data and performance requirements.