Searching Algorithms in C

Introduction

Searching algorithms are fundamental techniques in computer science used to find an element within a dataset. These algorithms can be classified into different categories based on their approach, efficiency, and the type of data structures they work on. This tutorial will cover the most common searching algorithms implemented in C, including Linear Search and Binary Search.

Linear Search

Linear search is the simplest searching algorithm. It checks each element of the list sequentially until the desired element is found or the list ends.

Algorithm

The basic idea is to iterate through the array and compare each element with the target element. If a match is found, return the index of the element. If no match is found after checking all elements, return -1.

Implementation in C

#include <stdio.h>

int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            return i;
        }
    }
    return -1;
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = linearSearch(arr, n, x);
    if (result == -1) {
        printf("Element is not present in array");
    } else {
        printf("Element is present at index %d", result);
    }
    return 0;
}
                

Element is present at index 3
                

Binary Search

Binary search is a much more efficient algorithm than linear search but requires the array to be sorted. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Algorithm

The basic steps of Binary Search are:

• Compare the target value to the middle element of the array.
• If the target value is equal to the middle element, return the index.
• If the target value is less than the middle element, repeat the search on the left half of the array.
• If the target value is greater than the middle element, repeat the search on the right half of the array.

Implementation in C

#include <stdio.h>

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;

        if (arr[m] == x) {
            return m;
        }

        if (arr[m] < x) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    if (result == -1) {
        printf("Element is not present in array");
    } else {
        printf("Element is present at index %d", result);
    }
    return 0;
}
                

Element is present at index 3
                

Conclusion

In this tutorial, we covered two fundamental searching algorithms: Linear Search and Binary Search. Linear Search is simple but inefficient for large datasets, while Binary Search is highly efficient but requires a sorted array. Understanding these algorithms provides a foundation for more advanced searching techniques and algorithms.