LINEAR AND BINARY SEARCH

Linear Search:

The linear search algorithm is a simple search algorithm that sequentially checks each element in a list or array until a match is found or the end of the list is reached. It starts at the beginning of the list and compares each element with the target value. If a match is found, the algorithm returns the index of the matching element. If the end of the list is reached without finding a match, the algorithm returns a special value to indicate that the target value is not present in the list.

Here is an example implementation of the linear search algorithm in C:

#include <stdio.h>

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // Return the index of the matching element
        }
    }
    return -1; // Return -1 if target value is not found
}

int main() {
    int arr[] = {5, 10, 15, 20, 25};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 15;
    int result = linearSearch(arr, n, target);
    if (result == -1) {
        printf("Target value not found\n");
    } else {
        printf("Target value found at index %d\n", result);
    }
    return 0;
}

Binary Search:

The binary search algorithm is a more efficient search algorithm compared to linear search, especially for large sorted lists or arrays. It works by repeatedly dividing the search space in half until the target value is found or the search space is empty.

To use the binary search algorithm, the list or array must be sorted in ascending order. The algorithm starts by comparing the target value with the middle element of the list. If the target value matches the middle element, the algorithm returns the index of the middle element. If the target value is less than the middle element, the algorithm continues the search on the left half of the list. If the target value is greater than the middle element, the algorithm continues the search on the right half of the list. This process is repeated until the target value is found or the search space is empty.

Here is an example implementation of the binary search algorithm in C:

#include <stdio.h>

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 matching element
        } else if (arr[mid] < target) {
            low = mid + 1; // Continue search on the right half
        } else {
            high = mid - 1; // Continue search on the left half
        }
    }
    return -1; // Return -1 if target value is not found
}

int main() {
    int arr[] = {5, 10, 15, 20, 25};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 15;
    int result = binarySearch(arr, 0, n - 1, target);
    if (result == -1) {
        printf("Target value not found\n");
    } else {
        printf("Target value found at index %d\n", result);
    }
    return 0;
}

In both linear search and binary search, the time complexity is O(n) and O(log n) respectively, where n is the number of elements in the list or array.