Last Updated on April 25, 2023 by Prepbytes
Linear search is a basic searching algorithm used in computer programming to find a specific element in a collection of data. It involves iterating through each element in the collection one by one until the target element is found. This algorithm is simple and easy to implement.
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.
Definition of Search in Computer Programming
In computer programming, the process of finding a particular item within a data structure is commonly known as search. This is often necessary when trying to extract useful information from a dataset.
For Example,
Let’s take the following example where we want to search for 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.
The linear search involves scanning an array or list sequentially until the desired element is found. If the value K is found during this process, it means that K is present in the array. Conversely, if K is not found after scanning through the entire array, it can be inferred 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 algorithm for Linear Search in Data Structure is given below in a stepwise manner.
- Initialize i = 0 and n = size of array
- 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.
- 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.
- 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
The dry run for linear search in data structure is given below for a better understanding of the topic.
Implementation of Linear Search in Data Structure
Below is a simple code implementation of Linear Search in Data Structure.
#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
The time complexity for the linear search in data structure is discussed below for different scenarios.
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.
Advantages of Linear Search In Data Structure
Linear search has several advantages which are listed below.
- It is a simple algorithm to implement and understand.
- It can be applied regardless of whether the array is sorted or not and is also compatible with arrays of different data types.
- Additionally, it does not require any extra memory to execute, making it efficient in terms of space usage.
- Linear search is particularly suitable for small datasets due to its straightforward nature.
Disadvantages of Linear Search In Data Structure
Here are some disadvantages of linear search in data structure.
- Its time complexity of O(n) can cause it to be slow when dealing with large datasets. Therefore, it may not be suitable for searching large arrays.
- Additionally, other search algorithms like hash tables may offer better efficiency in terms of time complexity.
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.
Frequently Asked Questions(FAQs)
Here are some frequently asked questions on linear search in data structure.
Ques 1. When is linear search most useful?
Ans. Linear search is most useful for small datasets where efficiency is not a primary concern and simplicity is preferred.
Ques 2. Can linear search be used for strings?
Ans. Yes, the linear search can be used for any data type, including strings.
Ques 3. How is linear search different from binary search?
Ans. Linear search in data structure iterates through each element in a collection sequentially, while binary search requires the collection to be sorted and search by dividing the collection in half and eliminating one-half of each iteration.
Ques 4. Is linear search the most efficient search algorithm?
Ans. No, linear search in data structure has a time complexity of O(n), meaning it can be inefficient for large datasets. Other search algorithms like binary search and hash tables may be more efficient.
Ques 5. Can linear search be used for linked lists?
Ans. Yes, linear search in data structure can be used for linked lists by iterating through each node in the list until the target element is found.