Program for Linear Search in C

Introduction

The linear search algorithm is a simple and direct way to look for a specific element inside an array. Each element in the array is successively checked until a match is discovered or the array's end. Beginning with the initial element, the algorithm compares it to the element that is being sought after. The algorithm returns the element's index if a match is discovered. If not, it advances to the following element and makes another comparison. This process continues until a match is made or the array's end is reached. The algorithm shows that the element is absent if the end of the array is reached without a match.

Since linear search has an O(n) time complexity, where n is the array size, it is appropriate for small-sized arrays or unsorted data. Other algorithms like binary search or hash-based approaches are typically favored for bigger arrays or more effective searches.

How Linear Search Works?

A list or array is systematically checked using the linear search method until the requested entry is located or the entire list has been scanned. A brute-force search algorithm is another term for it. Following is a list of the steps required to complete a linear search:

• Begin with the first item in the list.
• Compared with the current element, compare the target element.
• If the desired element is located, the search is finished, and the element's location is returned.
• Repeat steps 2 and 3 for the subsequent member in the list if the target element cannot be located.
• Continue doing this until you find the target element or come to the list’s end.
• If the target element cannot be found after searching to the end of the list, it is not in the list.

Let's consider an example to illustrate how linear search works. Suppose we have an array of numbers: [5, 9, 3, 7, 2]. We want to search for element 7 using linear search.

• Start at the beginning of the array: index 0.
• Compare the current element (5) with the target element (7). They are not equal.
• Move to the next element: index 1.
• Compare the current element (9) with the target element (7). They are not equal.
• Move to the next element: index 2.
• Compare the current element (3) with the target element (7). They are not equal.
• Move to the next element: index 3.
• Compare the current element (7) with the target element (7). They are equal.
• The target element (7) is found at index 3. The search is complete.
• Return index 3, indicating the position of the target element in the array.

This is how linear search works. It is a straightforward algorithm but may not be efficient for large lists as it requires traversing each element individually.

Program for Linear Search in C Using a Function

Here's an example of a C program that performs a linear search using a function:

#include <stdio.h>
int linear search(int arr[], int n, int target) {
    // Traverse the array
    for (int i = 0; i < n; i ) {
        // If the target element is found, return its index
        if (arr[i] == target) {
            return I;
        }
    }
    // If the target element is not found, return -1
    return -1;
}
int main() {
    int arr[] = {5, 9, 3, 7, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    // Perform linear search
    int result = linearSearch(arr, size, target);
    if (result == -1) {
        printf("Element not found\n");
    } else {
        printf("Element found at index %d\n", result);
    }
    return 0;
}

In this program, we define a function linearSearch that takes three arguments: the array to search (arr), the size of the array (n), and the target element to search for (target). The function returns the index of the target element if found or -1 if not found.

In the main function, we declare an array arr, determine its size, and specify the target element we want to search for (target = 7 in this example).

We then call the linearSearch function, passing in the array, size, and target element as arguments. The returned result is stored in the result variable.

Finally, we check the value of the result and print the appropriate message based on whether the element was found or not.

When you run this program, it will output the following:

An element found at index 3

This indicates that the target element 7 was found at index 3 in the array.

Linear Search Function Using Pointers

Here's an example of a C program that performs a linear search using a function with pointers:

#include <stdio.h>
int linear search(int *arr, int size, int target) {
    // Traverse the array
    for (int i = 0; i < size; i ) {
        // If the target element is found, return its index
        if (*arr == target) {
            return I;
        }
        arr; // Move the pointer to the next element
    }
    // If the target element is not found, return -1
    return -1;
}
int main() {
    int arr[] = {5, 9, 3, 7, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    // Perform linear search
    int result = linear search(arr, size, target);
    if (result == -1) {
        printf("Element not found\n");
    } else {
        printf("Element found at index %d\n", result);
    }
    return 0;
}

Complexity Analysis of Linear Search

The complexity analysis of an algorithm helps us understand how its performance scales with the size of the input. Let's analyze the complexity of the linear search algorithm:

In the worst-case scenario, the element being searched for is not present in the array, and we need to traverse the entire array to determine this. In the best-case scenario, the element is found at the first position in the array. The average case lies somewhere in between.

Time Complexity:

• Best case: O(1) - The target element is found at the first position in the array. In this case, we perform only one comparison.
• Worst case: O(n) - The target element is not present in the array, and we need to compare it with each element of the array, resulting in n comparisons, where n is the size of the array.
• Average case: O(n) - We expect to perform n/2 comparisons on average.

The linear search algorithm has a linear time complexity since the number of comparisons scales linearly with the size of the input array.

Space Complexity:

The space complexity of the linear search is O(1) because it does not require any additional space that grows with the size of the input. It uses constant space to store the variables for the loop iteration and the target element.

Advantages of Linear Search

The advantages of linear search include:

• Simplicity: Linear search is one of the simplest searching algorithms to understand and implement. It doesn't require any complex data structures or additional steps like sorting the array beforehand.
• Versatility: Linear search can be applied to various data structures, including arrays, linked lists, and other sequential structures. It works regardless of the order or organization of the elements.
• No preprocessing: Linear search requires no preprocessing or additional steps before searching. It can be used directly on the given data without any prior arrangements.
• Space efficiency: Linear search has a space complexity of O(1), meaning it requires only a constant amount of additional space regardless of the size of the input. It doesn't require additional data structures or memory allocations.
• Handles unsorted data: Linear search is effective for searching for unsorted data. It scans each data structure element sequentially until the target element is found, regardless of its position within the data.
• Early termination: Linear search can be optimized to terminate early if the target element is found before the data structure ends. This can save some execution time in certain cases.
• Suitable for small data sets: Linear search is well-suited for small data sets where the overhead of more complex search algorithms, such as binary search, may not be necessary. It provides a simple solution.

Drawbacks of Linear Search

Linear search also has some drawbacks, which include:

• Time complexity: In the worst-case scenario, when the target element is absent in the data structure, the linear search must traverse the entire structure and compare each element. This results in a time complexity of O(n), where n is the size of the data structure. As the data structure grows, the linear search becomes less efficient than other search algorithms with better time complexities.
• Inefficiency for large data sets: Linear search becomes increasingly inefficient as the size of the data structure increases. With a linear time complexity, the number of comparisons grows linearly with the size of the data structure. As a result, a linear search may not be practical or feasible for large-scale applications or datasets.
• Lack of early termination: In its basic implementation, the linear search must check every element in the data structure, even if the target element is found early on. This lack of early termination can lead to unnecessary comparisons and a waste of computational resources.
• Ineffective for sorted data: Linear search does not take advantage of any order or organization in the data structure. It scans each element sequentially, regardless of its position. This makes linear search inefficient for searching in sorted data, as it doesn't utilize the property of sorted order to optimize the search process.

Conclusion

linear search is a simple and versatile algorithm for searching elements in a data structure. It sequentially compares each element in the structure until the target element is found or the end of the structure is reached.

Therefore, when performance is crucial or dealing with larger or sorted data sets, alternative search algorithms with better time complexities, such as binary search or hash-based search, should be considered.

Ultimately, the choice of a search algorithm depends on the specific requirements, data characteristics, and trade-offs between simplicity and efficiency. Assessing the context and selecting the most suitable algorithm is essential.

FAQs

1. How does a linear search algorithm work in C?

Linear search sequentially checks each element in a list/array until the target is found or the end is reached.

2. What is the time complexity of linear search in C?

The time complexity of linear search is O(n), where n is the number of elements in the list/array.

3. How can I implement a linear search program in C?

Implement a loop to iterate through each element, comparing it with the target until a match is found.

4. What is the advantage of using pointers in a linear search program in C?

Pointers can be used to traverse the list/array efficiently without copying elements, saving memory and improving performance.