Linear Search In C

If there is an element to be found in a list or an array, a linear search algorithm can be used to find it. It is basically the way we search anything manually in an array also. If there is a long shelf with unlabelled boxes storing different hardware items and we need to find something specific, we logically start from one end and search to the other end until it is found. Similarly, linear search works by sequentially checking each element, starting from the first and going until the desired value is found or the end of the list is reached. 

Linear search is straightforward but can be inefficient for large datasets because it examines every element regardless of the list's size or order. Despite the inefficiency, it is a foundational algorithm that can be useful for unsorted data.

The linear search algorithm follows a straightforward approach to locate a target element in an array. Here's how it works step-by-step:

Step 1: Start from the first element. Begin at index 0 of the array and compare the target value (key) with the element at this index.

Step 2: Check for a match. If the key matches the current element, return its position immediately.

Step 3: Move to the next element. If there's no match, proceed to the next index and compare the key with the new element.

Step 4: Repeat the process. Continue checking each element in sequence until a match is found. Return to the position where the key is located.

Step 5: Handle unsuccessful searches. If the key is not found after checking all elements, display a message stating that the element is not in the array and exit the program.

The pseudocode of the above steps looks like this: 

procedure linear_search (list, value)
   for each item in the list
      if match item == value
         return the item's location
      end if
   end for
end procedure

Now let’s see how the linear search in data structure using c works: 

Consider an unsorted array to implement the search algorithm. It would be easier to understand using the example below. Let’s say we need to find the element K = 11 in the array. 

The algorithm starts from the first element and compares K with each element of the array. First element K is not 70, hence it moves to the next element.

K is not 40

K is not 30

K is 11

Now that the element is found, the algorithm returns the index of the element matched.

Now let’s implement the code to find an element in an array. In the following c program for linear search we will be looking for the element 10 and the program is supposed to get back with the answer saying the element is present at index 3.

#include <stdio.h>

int search(int arr[], int N, int x)
{
    for (int i = 0; i < N; i++)
        if (arr[i] == x)
            return i;
    return -1;
}

// Driver code
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int N = sizeof(arr) / sizeof(arr[0]);

    // Function call
    int result = search(arr, N, x);
    (result == -1)
        ? printf("Element is not present in array")

        : printf("Element is present at index %d", result);
    return 0;
}

Time Complexity:

Best Case: The key is found at the first index and requires only one comparison. Thus, the best case complexity is O(1).

Worst Case: The key is located at the last index, or it is not  present at all. In this scenario, the algorithm must traverse the entire list. It resulting in a worst-case complexity of O(N), where N is the size of the list.

Average Case: On average, the algorithm will search half the elements in the list before finding the key or concluding it’s absent. The average-case complexity is also O(N).

Space Complexity:

Linear search uses a constant amount of auxiliary space since it only requires a single variable to iterate through the list. Therefore, the space complexity is O(1).

Below is the code for the recursive implementation of linear search in c: 

#include <stdio.h>

// Define a function to perform the linear search
int linearSearch(int arr[], int size, int key)
{
    // If the size of the array is zero, return -1
    if (size == 0) {
        return -1;
    }

    // Check if the element at the current index
    // is equal to the key
    if (arr[size - 1] == key) {
        
        // If equal, return the index
        return size - 1;
    }
    // If not equal, call the function again
    // with the size reduced by 1
    return linearSearch(arr, size - 1, key);
}

// Driver code
int main()
{
    int arr[] = { 5, 15, 6, 9, 4 };
    int key = 4;
    int index
        = linearSearch(arr, sizeof(arr) / sizeof(int), key);
    if (index == -1) {
        printf("Key not found in the array.\n");
    }
    else {
        printf("The element %d is found at %d index of the "
               "given array \n",
               key, index);
    }
    return 0;
}

There are pros and cons of linear search Algorithm in c: 

Pros: 

• Works on both sorted and unsorted arrays.
• Can handle arrays of any data type.
• Requires no extra memory, making it space-efficient.
• Ideal for small datasets due to its simplicity.

Cons: 

• Inefficient for large datasets with a time complexity of O(N).
• It is not suitable for searching in large arrays as it becomes slow and resource-intensive.

1. Simple for beginners: Linear search is easy to implement and understand. Therefore, it’s a practical choice for beginners to learn with simpler use cases. 
2. Unsorted Lists: Linear search is often the basic method for searching elements in unsorted arrays or lists since it doesn’t require prior sorting.
3. Searching Linked Lists: In linked list structures, linear search is widely used to locate elements. Each node is traversed sequentially until the target value is found. 
4. Small Data Sets: For smaller datasets, linear search is preferred over algorithms like binary search due to its straightforward logic and minimal overhead. 

That concludes the introduction to the topic of linear search in c. With the examples given, you should be able to understand the concepts and apply them to other searching problems. It’s important to solve more advanced search examples, and the best place to learn would be a tailored program that prepares you for real-world jobs. Enroll in CCBP 4.0 Academy today to start on your professional journey.

1. What is a linear search algorithm?

Linear search in C is a simple algorithm for searching. It checks each element in a list sequentially to find the target value.

2. How does the linear search algorithm work?

The algorithm starts from the first element and compares each one with the target. Once a match is found it returns the value or the list ends without the target being in the list.

3. When is the linear search algorithm preferred over other searching algorithms?

Linear search is preferred for unsorted data, small datasets. It’ also used when simplicity in implementation is required.

4. Can the linear search algorithm in C be applied to other data structures?

Yes, linear search in data structure using c is often used in arrays, linked lists, or any collection that allows sequential traversal.

5.What are some real-world applications of linear search algorithms?

Linear search is used in tasks like looking up names in unsorted directories or searching for specific values in small datasets.