Linear Search in arrays in C

Linear search, also known as sequential search, is one of the simplest searching algorithms used in computer science to find a particular element in a list. It works by sequentially checking each element of the list until a match is found or the whole list has been searched. This method is straightforward and does not require the array to be sorted, unlike other search algorithms like binary search.

Introduction to Linear Search

Searching algorithms are essential in computing for locating elements within data structures. Among these, linear search is the most basic form, characterized by its simplicity and lack of prerequisites regarding the order of elements. It contrasts with more complex algorithms such as binary search, which requires a sorted array, or hash tables, which need a more sophisticated data structure. Linear search operates by comparing each element in the array to the target value sequentially, making it an intuitive approach but potentially inefficient for large datasets.

How Linear Search Works

To understand how linear search works, consider an array of elements. The algorithm starts at the first element and compares it with the target value. If the target value is not found, it moves to the next element and repeats the process until the target is found or the end of the array is reached. This can be visualized or represented using pseudo-code as follows:

for each item in the array
    if item is equal to the target value
        return the current index
end for
return not found

Understanding the Linear Search Algorithm

The efficiency of linear search depends on the position of the target element within the array. In the best-case scenario, the target is the first element, resulting in a single comparison. In the worst case, the target is the last element or not present, requiring n comparisons (where n is the number of elements in the array). This demonstrates linear search’s O(n) time complexity, where the time to complete the search grows linearly with the number of elements.

Linear Search Example

Imagine an array of integers: [4, 2, 5, 1, 3], and you want to find the position of the number 1. Using linear search, you would start with the first element:

Compare 4 to 1 – no match.
Move to the next element, compare 2 to 1 – no match.
Continue to 5, then to 1 – a match is found.

The algorithm identifies the position of 1 in the array as being the fourth element.

Implementing Linear Search in C

The C programming language, known for its control over low-level mechanisms, is ideal for implementing simple algorithms like linear search. The implementation requires familiarity with basic C syntax, including loops and conditionals.

Basic Syntax and Structure of C for Linear Search

A linear search function in C might be structured as follows: it accepts an array and the target value as parameters and returns the index of the target if found, or an indicator that the target is not present. The function signature could look like:

int linearSearch(int arr[], int size, int target) {

    // Implementation goes here

}

Writing a Linear Search Program in C

Here’s a step-by-step guide to implementing the linear search algorithm in C:

1#include <stdio.h>

2

3int linearSearch(int arr[], int size, int target) {

4    for (int i = 0; i < size; i++) {

5        if (arr[i] == target) {

6            return i; // Return the index of the target

7        }

8    }

9    return -1; // Target not found

10}

11

12int main() {

13    int array[] = {4, 2, 5, 1, 3};

14    int target = 1;

15    int size = sizeof(array) / sizeof(array[0]);

16    int result = linearSearch(array, size, target);

17    if (result != -1) {

18        printf("Element found at index: %d\n", result);

19    } else {

20        printf("Element not found in the array.\n");

21    }

22    return 0;

23}

Explanation

Linear search, also known as sequential search, is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been checked. Here’s a step-by-step explanation of how the linear search algorithm works in C:

Start from the first element: Begin by examining the first element of the array.
Compare the current element with the target value: If the current element matches the target value, the search ends with success.
Move to the next element: If the current element does not match the target value, proceed to the next element in the array.
Repeat the process: Continue steps 2 and 3 until the target value is found or the end of the array is reached.
Return the index of the target value: If the target value is found, return its index. Otherwise, return -1 or an indication that the search was unsuccessful.

Complexity Analysis of Linear Search

Time Complexity

The time complexity of linear search is O(n), where n is the number of elements in the array. This means that in the worst-case scenario, the algorithm will have to check each element once. For example, if there are 100 items in the array and the target value is the last item, linear search will make 100 comparisons.

Space Complexity

The space complexity of linear search is O(1), indicating that the amount of memory used does not depend on the size of the input array. This is because linear search only requires a constant amount of space to store temporary variables, regardless of the array size.

Best-case, Average-case, and Worst-case Scenarios

Best-case scenario: The target value is the first element of the array. Here, the complexity is O(1).
Average-case scenario: On average, the target value is located about halfway through the array, resulting in a complexity of O(n/2). However, in Big O notation, this is still expressed as O(n).
Worst-case scenario: The target value is the last element of the array or not present at all, requiring n comparisons and resulting in O(n) complexity.

Advantages and Disadvantages of Linear Search

Advantages

Simplicity: Linear search is straightforward to understand and implement, making it suitable for small datasets.
No need for sorted data: Unlike binary search, linear search does not require the array to be sorted, offering flexibility in its application.

Disadvantages

Inefficiency on large datasets: As the size of the dataset increases, the time it takes to find an element (or determine its absence) increases linearly, which can be impractical for large arrays.

Practical Applications of Linear Search

Linear search is particularly useful in scenarios where:

The dataset is small.
The data is unsorted and cannot be efficiently sorted for some reason.
The simplicity of implementation is prioritized over search efficiency.

Why Choose Linear Search

Linear search is chosen in scenarios where the ease of implementation outweighs the efficiency drawbacks, such as when dealing with small or unsorted datasets where the overhead of more complex algorithms is not justified.