Linear Search in Data Structure

A very straightforward search algorithm is linear search in data structure. In this kind of search, each item is sequentially searched through. Each item is examined, and if a match is discovered, that specific item is returned; otherwise, the search is carried out until all the data have been collected.

One of the most widely applied programming techniques in daily life is searching. It’s everywhere, whether you’re browsing on Google, shopping on Amazon, or discovering the next Netflix series to binge. If you stop to think about it, you probably found this article by searching on Google or possibly Bing alone today.

Searching Definition

Finding useful information in a data set is done by searching.

Finding a specific piece in a data structure is commonly referred to as searching in computer programming. Let’s take the following example where we want to discover the word "PrepBytes" in the sentence:

“Learn coding from PrepBytes”

PrepBytes is the fourth word in the previous statement, as can be seen. When the data set is so little and you are using your naked sight to search, that is simple.

It won’t be so simple, though, if someone asks you to locate a word in a text that has tens of thousands of words and sentences.

That’s exactly what we’ll study today: how to write a program to find an element in a data set.

Linear Search In Data Structure

Let’s imagine that we are attempting to find the value K within an array of random integers.

Suppose the array is 5 3 12 9 45 1 22
K = 9 is the value of the element we’re looking for.

What is the most logical approach to take?
You’ve just defined Linear Search yourself if you’re planning to start at the beginning of the array and see if each element is equal to K or not until you either find K or reach the end.

Let’s give it a clearer definition.

In a linear search, we go over each element of the array one at a time and see if it matches the element we’re looking for. Because it examines each element in turn, it is also known as a sequential search.

Finding an element with the value K indicates that K is present in the array. If we reach the end and K is nowhere to be seen, we know that K is not in the array. Let’s try using linear search for the input mentioned above.

5 3 12 9 45 1 22 – Found K = 9 at index 3

Working of Linear Search In Data Structure Algorithm

As you can see, in the fourth comparison, we found K.

You could counter that there is no need to begin at the beginning rather than the middle or the end. We can carry out either of those, you’re right. But consider this: Does it truly assist? No, really, is the response.

Only the fourth iteration contains the number 9 if you attempt to search for it from the end rather than the beginning.

5 3 12 9 45 1 22 – Found K = 9 at index 3

What is Linear Search In Data Structure Algorithm?

If K is present in the first half of the array, it will be simpler to start at the beginning if K is present. On the other hand, it is preferable to begin at the end if it appears in the second part.

But stop and think about it—do we really know where the element might be in a wholly random array? Or maybe just the fact that it exists or not? Right, we don’t. We use linear search for that purpose.

In fact, it is very possible that K will be the first element of the array if you start at the end and the last if you start from the first.

As a result, if we assume the worst, we will always end up searching the entire array. Therefore, it doesn’t really matter where we begin the search.

Algorithm For Linear Search In Data Structure

The linear search algorithm is shown below.

  1. Initialize i = 0 and n = size of array
  2. If i >= n, which means we have reached the end of the array and we could not find K. We return -1 to signify that the element K was not found.
  3. If arr [ i ] == K, it means that we have found an element that is equal to K at index ‘i’ and we do not need to search the remaining array.We immediately return the value i from here, which is the index in this array at which K was located.
  4. If arr [i]!= K, the current element of the array will not equal K, and we will repeat step 2 with the subsequent element by incrementing i i.e. ++i.

Dry Run For Linear Search In Data Structure

Implementation

Below is a simple implementation of Linear Search.

#include <stdio.h>

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;
} else {
    // If not equal, call the function again with the size reduced by 1
    return linearSearch(arr, size - 1, key);
}
}

int main() {

int arr[] = {5, 2, 3, 4, 17, 21, 71, 10, 12, 14, 31};
int key = 71;
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;
}
#include <iostream>
using namespace std;

int linearsearch(int arr[], int size, int key)
{
    if (size == 0) {
        return -1;
    }
    else if (arr[size - 1] == key) {
        // Return the index of found key.
        return size - 1;
    }
    else {
        int ans = linearsearch(arr, size - 1, key);
        return ans;
    }
}

int main()
{
    int arr[11] = {5, 2, 3, 4, 17, 21, 71, 10, 12, 14, 31};
    int key = 71;

    // Function call
    int ans = linearsearch(arr, 11, key);
    if (ans == -1) {
        cout << "The element " << key << " is not found."
            << endl;
    }
    else {
        cout << "The element " << key << " is found at "
            << ans << " index of the given array." << endl;
    }
    return 0;
}
import java.io.*;

class Test {
    static int arr[] = {5, 2, 3, 4, 17, 21, 71, 10, 12, 14, 31};

    // Recursive Method to search key in the array
    static int linearsearch(int arr[], int size, int key)
    {
        if (size == 0) {
            return -1;
        }
        else if (arr[size - 1] == key) {
            // Return the index of found key.
            return size - 1;
        }
        else {
            return linearsearch(arr, size - 1, key);
        }
    }


    public static void main(String[] args)
    {
        int key = 71;

        // Function call to find key
        int index = linearsearch(arr, arr.length, key);
        if (index != -1)
            System.out.println(
                "The element " + key + " is found at "
                + index + " index of the given array.");

        else
            System.out.println("The element " + key
                            + " is not found.");
    }
}
def linear_search(arr, key, size):

# If the array is empty we will return -1
    if (size == 0):
        return -1

    elif (arr[size - 1] == key):
        # Return the index of found key.
        return size - 1
    else:
        return linear_search(arr, key, size - 1)


if __name__ == "__main__":
    arr = [5, 2, 3, 4, 17, 21, 71, 10, 12, 14, 31]
    key = 71
    size = len(arr)
    ans = linear_search(arr, key, size) # Calling the Function
    if ans != -1:
        print("The element", key, "is found at",
            ans, "index of the given array.")
    else:
        print("The element", key, "is not found.")

Output

The element 71 is found at 6 index of the given array.

Time Complexity For Linear Search In Data Structure

Here is a straightforward linear search implementation.

In the best-case scenario, K, which is the first element of the array, might only be found in the first iteration.

In the worst scenario, K might not even be present in the array by the time we reach the final iteration.

It might typically be found anywhere in the middle of the array.

The average case time complexity of the linear search is therefore probably O(n/2) ~ O(n), where n is the number of elements in the array. Consequently, the linear search’s time complexity is, in fact, linear.

Space Complexity For Linear Search In Data Structure

It is clear that we do not significantly increase our memory usage for linear search. As a result, the space complexity is constant, or O(1).

Note: Since they are independent of the input size of the array, the variables used to iterate the array and other minor information are constant.

Applications For Linear Search In Data Structure

The most straightforward and simple to use and understand algorithm is linear search. Since it always consumes constant memory, it is especially helpful when the data set is tiny, randomized, and there are memory restrictions.

Since linear search will take linear time in each case on average, it is not the most effective strategy when searching several elements in a data collection.

Conclusion
The process of searching is pretty fascinating, especially to me because there are so many uses for it and so many obstacles to overcome in order to search well. It’s also one of the most frequent interview topics. So put on your hunting boots and start looking.

Leave a Reply

Your email address will not be published. Required fields are marked *