Search Algorithms

According to Wikipedia, a search algorithm is:

An algorithm designed to address the search problem involves retrieving specific information stored within a data structure or computed within the search space of a problem domain. This search can encompass both discrete and continuous values.

Search algorithms are used to locate specific items within a collection of items

Types of Search Algorithms

• Linear Search.

• Sentinel Linear Search.

• Binary Search.

• Meta Binary Search | One-Sided Binary Search.

• Ternary Search.

• Jump Search.

• Interpolation Search.

• Exponential Search.

In this article, we are going to discuss two important types of search algorithms which are

1. Linear Search

2. Binary Search

Linear search

Also known as sequential search, is one of the most straightforward search algorithms. It is used to find a specific element in a list by checking each element one by one, starting from the beginning of the list until a match is found or the end of the list is reached.

#include <stdio.h>
int linear_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // Return the index if the target element is found
        }
    }
    return -1; // Return -1 if the target element is not in the list
}
int main() {
    int my_array[] = {4, 2, 7, 1, 9, 5};
    int target_element = 7;
    int size = sizeof(my_array) / sizeof(my_array[0]);
    int result = linear_search(my_array, size, target_element);

    if (result != -1) {
        printf("Element %d found at index %d.\n", target_element, result);
    } else {
        printf("Element %d not found in the list.\n", target_element);
    }
    return 0;
}

In this C implementation, the linear_search function takes an array (arr), its size (n), and the target element (target) as parameters. It iterates through the array, comparing each element with the target. If a match is found, the function returns the index of the target element. If the target element is not found, the function returns -1.

In the main function, an example array my_array is defined, and the linear_search function is called to search for the target element (7). The result is then printed to the console.

Binary Search:

Binary search is a fast and efficient search algorithm used to locate a specific item in a sorted collection (like an array) by repeatedly dividing the search space in half. It's similar to how you might look up a word in a dictionary: you open the dictionary in the middle, decide whether the word you're looking for would be in the first half or the second half, and continue searching in that half.

#include <stdio.h>

int binary_search(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // Check if the target is present at the middle
        if (arr[mid] == target) {
            return mid; // Return the index if the target element is found
        }
        // If the target is greater, ignore the left half
        if (arr[mid] < target) {
            left = mid + 1;
        }
        // If the target is smaller, ignore the right half
        else {
            right = mid - 1;
        }
    }
    return -1; // Return -1 if the target element is not in the list
}
int main() {
    int my_array[] = {1, 2, 4, 5, 7, 9};
    int target_element = 7;
    int size = sizeof(my_array) / sizeof(my_array[0]);

    int result = binary_search(my_array, 0, size - 1, target_element);

    if (result != -1) {
        printf("Element %d found at index %d.\n", target_element, result);
    } else {
        printf("Element %d not found in the list.\n", target_element);
    }
    return 0;
}

In this example, the binary_search function takes an array, the left and right indices representing the current search range, and the target element as parameters. The function iteratively divides the search space in half until the target element is found or the search space is empty. The main function demonstrates how to use the binary_search function.