Searching Algorithms in C Programming Language

Searching algorithms are fundamental techniques used in computer science to locate specific elements within a data structure. Whether you’re looking for a particular value in an array or a node in a linked list, efficient searching algorithms are crucial for solving a wide range of problems.

In this blog article, we’ll explore some common searching algorithms implemented in the C programming language.

1. Linear Search:

Linear search, also known as sequential search, is a simple searching algorithm used to find a target value within a collection (such as an array or a list). It works by sequentially checking each element of the collection until the target value is found or the entire collection has been traversed.

Here’s how the linear search algorithm works:

1. Start at the Beginning: The algorithm begins by checking the first element of the collection.
2. Compare: It compares the target value with the current element being examined.
3. Match Found?: If the current element matches the target value, the search is complete, and the index of the element is returned as the result.
4. Move to the Next Element: If the current element does not match the target value, the algorithm moves to the next element in the collection and repeats steps 2 and 3.
5. Repeat Until the End: The algorithm continues this process until either the target value is found or the entire collection has been traversed.
6. Target Not Found: If the target value is not found after examining all elements in the collection, the algorithm returns a special value (such as -1) to indicate that the target value is not present in the collection.

Here’s a simple implementation of the linear search algorithm in C:

int linearSearch(int arr[], int n, int target) {
    // Iterate through each element in the array
    for (int i = 0; i < n; i++) {
        // If the current element matches the target value, return its index
        if (arr[i] == target) {
            return i;
        }
    }
    // If the target value is not found, return -1
    return -1;
}

In this implementation:

• arr[] is the array to be searched.
• n is the number of elements in the array.
• target is the value being searched for.

The function returns the index of the target value if found, or -1 if the target value is not present in the array.

Linear search is straightforward and easy to implement, but it is not very efficient for large collections, especially when compared to more advanced search algorithms like binary search. However, it can still be useful in situations where the collection is small or unsorted, or when a simple solution is sufficient.

2. Binary Search:

Binary search on the other hand is an efficient searching algorithm used to find a target value within a sorted collection (such as an array). It works by repeatedly dividing the search interval in half until the target value is found or the search interval becomes empty.

Here’s how the binary search algorithm works:

1. Start with a Sorted Collection: Binary search requires that the collection be sorted in ascending order beforehand. If the collection is not sorted, it needs to be sorted first.
2. Define the Search Interval: Initially, the algorithm considers the entire collection as the search interval.
3. Find the Middle Element: It calculates the middle element of the current search interval.
4. Compare with the Target Value: It compares the middle element with the target value.
5. Target Value Found?: If the middle element is equal to the target value, the search is complete, and the index of the middle element is returned as the result.
6. Adjust the Search Interval: If the middle element is greater than the target value, the search interval is narrowed to the lower half (excluding the middle element). Similarly, if the middle element is less than the target value, the search interval is narrowed to the upper half (excluding the middle element).
7. Repeat Until Found or Interval Is Empty: Steps 3-6 are repeated until either the target value is found or the search interval becomes empty.
8. Target Not Found: If the target value is not found after narrowing down the search interval to an empty set, the algorithm returns a special value (such as -1) to indicate that the target value is not present in the collection.

Here’s a simple implementation of the binary search algorithm in C:

int binarySearch(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid; // Return the index of the target element
        } else if (arr[mid] < target) {
            low = mid + 1; // Narrow down the search interval to the upper half
        } else {
            high = mid - 1; // Narrow down the search interval to the lower half
        }
    }
    return -1; // Return -1 if the target element is not found
}

In this implementation:

• arr[] is the sorted array to be searched.
• low and high represent the indices of the current search interval.
• target is the value being searched for.

The function returns the index of the target value if found, or -1 if the target value is not present in the array.

Binary search is significantly more efficient than linear search for large collections, especially when the collection is sorted. It has a time complexity of O(log n), where n is the number of elements in the collection. However, binary search requires that the collection be sorted beforehand, which can be an additional overhead if the collection is frequently updated or modified.

3. Interpolation Search:

Finally, interpolation search is an efficient searching algorithm used to find a target value within a sorted, uniformly distributed collection (such as an array). It improves upon binary search by making intelligent guesses about the position of the target value based on the distribution of elements in the collection.

Here’s how the interpolation search algorithm works:

1. Start with a Sorted Collection: Similar to binary search, interpolation search requires that the collection be sorted in ascending order beforehand. If the collection is not sorted, it needs to be sorted first.
2. Calculate the Probable Position: Instead of always dividing the search interval in half like binary search, interpolation search calculates the probable position of the target value based on its value and the distribution of elements in the collection.
3. Guess the Position: Interpolation search uses an interpolation formula to make an educated guess about the position of the target value within the collection. The interpolation formula estimates the probable position based on the value of the target and the range of values in the collection.
4. Compare with the Target Value: It compares the value at the guessed position with the target value.
5. Target Value Found?: If the value at the guessed position matches the target value, the search is complete, and the index of the guessed position is returned as the result.
6. Adjust the Search Interval: Depending on whether the value at the guessed position is greater or less than the target value, the search interval is adjusted accordingly to narrow down the search space.
7. Repeat Until Found or Interval Is Empty: Steps 3-6 are repeated until either the target value is found or the search interval becomes empty.
8. Target Not Found: If the target value is not found after narrowing down the search interval to an empty set, the algorithm returns a special value (such as -1) to indicate that the target value is not present in the collection.

Interpolation search adapts its search strategy based on the distribution of values in the collection, making it more efficient than binary search, especially when the collection is uniformly distributed. However, if the distribution of values is highly irregular, interpolation search may not perform as well as binary search.

Here’s a simple implementation of the interpolation search algorithm in C:

int interpolationSearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high && target >= arr[low] && target <= arr[high]) {
        int pos = low + ((double)(high - low) / (arr[high] - arr[low])) * (target - arr[low]);
        if (arr[pos] == target) {
            return pos; // Return the index of the target element
        } else if (arr[pos] < target) {
            low = pos + 1;
        } else {
            high = pos - 1;
        }
    }
    return -1; // Return -1 if the target element is not found
}

In this implementation:

• arr[] is the sorted array to be searched.
• n is the number of elements in the array.
• target is the value being searched for.

The function returns the index of the target value if found, or -1 if the target value is not present in the array.

Conclusion:

Searching algorithms are essential tools in the arsenal of every programmer. By understanding and implementing efficient searching algorithms, you can improve the performance of your programs and solve a variety of problems more effectively.

In this article, I’ve covered some of the most commonly used searching algorithms in C programming, including linear search, binary search, and interpolation search. These algorithms form the foundation of many applications and provide valuable insight into the principles of algorithm design and analysis.

As you continue your journey in programming and computer science, mastering searching algorithms will be key to your success.