C-Language-Series-#128-Implementing-Searching-Algorithms-in-C

Welcome to another installment of our C Language Series! In the realm of computer science, efficient data handling is paramount, and a fundamental operation we frequently perform is finding specific information within a collection of data. This process is handled by what we call searching algorithms. Whether you're sifting through a database, looking up a contact in a phone book, or finding a specific item in an inventory, searching is at the core of many applications.

In this post, we'll dive deep into implementing some of the most common searching algorithms using C. Understanding these algorithms is crucial not just for competitive programming but also for building robust and performant software.

What are Searching Algorithms?

At its core, a searching algorithm is a method designed to retrieve an element from a data structure (like an array, linked list, tree, etc.) or to determine its absence. The efficiency of a search algorithm is often measured by its time complexity, which describes how the execution time grows with the size of the input data.

We'll primarily focus on searching within arrays, as they provide a clear foundation for understanding the mechanics of these algorithms.

1. Linear Search (Sequential Search)

The simplest of all searching algorithms, linear search, as its name suggests, works by sequentially checking each element in the list until a match is found or the entire list has been traversed. It's straightforward and doesn't require the data to be sorted.

How it Works:

1. Start from the first element of the array.
2. Compare the current element with the target value.
3. If they match, the element is found, and its index is returned.
4. If they don't match, move to the next element.
5. Repeat until the end of the array is reached.
6. If the end is reached and no match is found, the element is not present.

Time Complexity:

• Worst Case: O(n) - The target element is at the very end or not present at all.
• Best Case: O(1) - The target element is the first element.
• Average Case: O(n)

This makes linear search suitable for small arrays or unsorted data where the overhead of sorting might outweigh the benefits of a faster search.

C Code Example:

Let's implement a function for linear search:

#include <stdio.h>

// Function to perform linear search
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // Target found, return its index
        }
    }
    return -1; // Target not found
}

int main() {
    int numbers[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int n = sizeof(numbers) / sizeof(numbers[0]); // Calculate array size
    int target1 = 50;
    int target2 = 95;

    // Search for target1
    int index1 = linearSearch(numbers, n, target1);
    if (index1 != -1) {
        printf("Target %d found at index: %d\n", target1, index1);
    } else {
        printf("Target %d not found in the array.\n", target1);
    }

    // Search for target2
    int index2 = linearSearch(numbers, n, target2);
    if (index2 != -1) {
        printf("Target %d found at index: %d\n", target2, index2);
    } else {
        printf("Target %d not found in the array.\n", target2);
    }

    return 0;
}

Output:

Target 50 found at index: 4
Target 95 not found in the array.

2. Binary Search

Binary search is a significantly more efficient algorithm compared to linear search, but it comes with a crucial prerequisite: the data must be sorted. It operates on the principle of "divide and conquer," repeatedly dividing the search interval in half.

How it Works:

1. Initialize two pointers, low (pointing to the first element) and high (pointing to the last element).
2. While low is less than or equal to high:
   1. Calculate the mid index: mid = low + (high - low) / 2 (this prevents potential overflow compared to (low+high)/2).
   2. If the element at mid is the target value, the element is found, and its index is returned.
   3. If the element at mid is less than the target, it means the target must be in the right half of the current interval. Update low = mid + 1.
   4. If the element at mid is greater than the target, it means the target must be in the left half. Update high = mid - 1.
3. If the loop finishes without finding the target, it's not present in the array.

Time Complexity:

• Worst Case: O(log n)
• Best Case: O(1) - The target element is at the middle.
• Average Case: O(log n)

The logarithmic complexity means that binary search is incredibly fast for large datasets, as it halves the search space with each comparison.

C Code Example (Iterative):

#include <stdio.h>

// Function to perform iterative binary search
int binarySearchIterative(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // Calculate mid-point

        if (arr[mid] == target) {
            return mid; // Target found
        } else if (arr[mid] < target) {
            low = mid + 1; // Target is in the right half
        } else {
            high = mid - 1; // Target is in the left half
        }
    }
    return -1; // Target not found
}

int main() {
    int sortedNumbers[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int n = sizeof(sortedNumbers) / sizeof(sortedNumbers[0]);
    int target1 = 70;
    int target2 = 25;

    // Search for target1
    int index1 = binarySearchIterative(sortedNumbers, n, target1);
    if (index1 != -1) {
        printf("Target %d found at index: %d\n", target1, index1);
    } else {
        printf("Target %d not found in the array.\n", target1);
    }

    // Search for target2
    int index2 = binarySearchIterative(sortedNumbers, n, target2);
    if (index2 != -1) {
        printf("Target %d found at index: %d\n", target2, index2);
    } else {
        printf("Target %d not found in the array.\n", target2);
    }

    return 0;
}

Output:

Target 70 found at index: 6
Target 25 not found in the array.

C Code Example (Recursive - Optional but common):

#include <stdio.h>

// Function to perform recursive binary search
int binarySearchRecursive(int arr[], int low, int high, int target) {
    if (low > high) {
        return -1; // Base case: Target not found
    }

    int mid = low + (high - low) / 2;

    if (arr[mid] == target) {
        return mid; // Target found
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, mid + 1, high, target); // Search right half
    } else {
        return binarySearchRecursive(arr, low, mid - 1, target); // Search left half
    }
}

int main() {
    int sortedNumbers[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int n = sizeof(sortedNumbers) / sizeof(sortedNumbers[0]);
    int target1 = 30;
    int target2 = 110;

    // Search for target1
    int index1 = binarySearchRecursive(sortedNumbers, 0, n - 1, target1);
    if (index1 != -1) {
        printf("Target %d found at index: %d\n", target1, index1);
    } else {
        printf("Target %d not found in the array.\n", target1);
    }

    // Search for target2
    int index2 = binarySearchRecursive(sortedNumbers, 0, n - 1, target2);
    if (index2 != -1) {
        printf("Target %d found at index: %d\n", target2, index2);
    } else {
        printf("Target %d not found in the array.\n", target2);
    }

    return 0;
}

Output:

Target 30 found at index: 2
Target 110 not found in the array.

Choosing the Right Algorithm

The choice between linear and binary search boils down to the nature of your data and the requirements of your application:

• Use Linear Search when:
  • The data is unsorted.
  • The dataset is small (performance difference is negligible).
  • You only need to perform a search once or very infrequently.
• Use Binary Search when:
  • The data is sorted (or you can afford to sort it first).
  • The dataset is large (O(log n) provides significant performance benefits).
  • You need to perform multiple searches on the same dataset.

While we've covered the two most fundamental searching algorithms, it's worth noting that many other specialized searching techniques exist, such as jump search, interpolation search, hash-based searching, and searches on tree data structures (like BSTs or B-trees). These are often optimized for specific scenarios and data structures.

Conclusion

Searching algorithms are fundamental building blocks in computer science. Linear search offers simplicity for unsorted or small datasets, while binary search provides exceptional efficiency for sorted, larger collections. Mastering these algorithms is a critical step in becoming a proficient C programmer and understanding the performance implications of your code.

Experiment with these implementations, try modifying them, and think about their behavior with different inputs. In upcoming posts, we'll explore other core algorithms like sorting, which often go hand-in-hand with efficient searching.