Searching Algorithms: An Overview and Implementation

Searching algorithms are used to find a specific value within a collection of data. There are many different searching algorithms, each with its own strengths and weaknesses. In this article, we will explore the most commonly used searching algorithms and their implementation.

Linear Search

Linear search is a simple searching algorithm that involves sequentially searching through a collection of data to find a specific value. This algorithm is easy to implement but can be inefficient for large datasets. The time complexity of linear search is O(n).

Implementation:

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

Binary Search

Binary search is a more efficient searching algorithm that works by repeatedly dividing the search interval in half until the target value is found. Binary search is only applicable to sorted datasets. The time complexity of binary search is O(log n).

Implementation:

int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) {
            return mid;
        }
        if (arr[mid] > x) {
            return binarySearch(arr, l, mid - 1, x);
        }
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}

Interpolation Search

Interpolation search is an improvement over binary search that works by calculating the probable position of the target value based on the distribution of the data. This algorithm is more efficient than binary search for datasets with a non-uniform distribution. The time complexity of interpolation search is O(log log n) on average.

Implementation:

int interpolationSearch(int arr[], int n, int x)
{
    int lo = 0, hi = (n - 1);
    while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
        if (lo == hi) {
            if (arr[lo] == x) return lo;
            return -1;
        }
        int pos = lo + (((double)(hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));
        if (arr[pos] == x) {
            return pos;
        }
        if (arr[pos] < x) {
            lo = pos + 1;
        }
        else {
            hi = pos - 1;
        }
    }
    return -1;
}

Hashing

Hashing is a searching algorithm that works by converting the search key into a hash code, which is used to index a table of values. This algorithm is efficient for large datasets, but can have collisions that reduce performance. The time complexity of hashing is O(1) on average.

Implementation:

int hashFunction(int key)
{
    return key % TABLE_SIZE;
}

int search(int key)
{
    int index = hashFunction(key);
    while (hashTable[index] != NULL) {
        if (hashTable[index]->key == key) {
            return hashTable[index]->value;
        }
        index++;
        index %= TABLE_SIZE;
    }
    return -1;
}

Conclusion

Searching algorithms are an important part of computer science and are used to find specific values within a collection of data. The choice of searching algorithm depends on the characteristics of the dataset and the efficiency required. Linear search, binary search, interpolation search, and hashing are some of the most commonly used searching algorithms. Implementing