Example usage

In the previous article, we introduced common sorting algorithms, which help organize data into an ordered sequence. Next, we will discuss another essential class of algorithms—searching algorithms. These algorithms are designed to quickly locate a specific element within a dataset. Searching algorithms are indispensable in programming, especially when efficiency becomes critical for large datasets.

Linear Search

Overview

Linear search is the simplest searching algorithm. It sequentially examines each element until the target value is found or the entire array has been traversed. Its time complexity is $O(n)$, where $n$ is the number of elements in the dataset.

Example

Suppose we have an array arr and a target value target, and we wish to locate target within arr.

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

# Example usage
arr = [5, 3, 8, 6, 2]
target = 6
result = linear_search(arr, target)

if result != -1:
    print(f"Target {target} found at index {result}.")
else:
    print("Target not found.")

In this example, linear search locates the index of target value 6. Because linear search inspects each array element one by one, its efficiency diminishes significantly for very large arrays.

Binary Search

Overview

Binary search is a more efficient searching algorithm—but it works only on sorted arrays. It repeatedly halves the search interval, comparing the target with the middle element: if the target is smaller, the search continues in the left half; otherwise, it proceeds in the right half. Its time complexity is $O(\log n)$.

Example

Using binary search to locate a target value—provided the array is already sorted.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # Prevents integer overflow
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1  # Return -1 if not found

# Example usage
arr = [2, 3, 5, 6, 8]  # Must be a sorted array
target = 6
result = binary_search(arr, target)

if result != -1:
    print(f"Target {target} found at index {result}.")
else:
    print("Target not found.")

In this example, binary search rapidly pinpoints the location of target 6 by halving the search space at each step. Its key advantage lies in drastically reducing the number of comparisons required.

Choosing the Right Search Algorithm

When implementing a search algorithm, select the appropriate one based on your dataset’s characteristics:

1. For unsorted data, use linear search, as it imposes no ordering requirements.
2. For sorted data, prefer binary search to achieve significantly higher efficiency.

Summary

In this article, we covered two fundamental searching algorithms: linear search and binary search. Selecting the appropriate search strategy during data processing can substantially improve program performance. In the next installment, we will explore recursive algorithms—a vital programming technique that plays a central role in many algorithm implementations.

We hope this section helps you better understand searching algorithms!