EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login

Linear Search in Data Structure

Home » Data Science » Data Science Tutorials » Data Structures Tutorial » Linear Search in Data Structure

Linear-Search-in-Data-Stucture

Introduction to Linear Search in Data Structure

One of the very simplest methods to search an element in an array is a linear search. This method uses a sequential approach to search the desired element in the list. If the element is successfully found in the list, then the index of that element is returned. The search starts from the first element and sequentially proceeds in the forward direction.

Algorithm for Linear Search in Data Structure

The algorithm for linear search is as shown below. It is a straightforward algorithm. Go through it and study it as we shall be building a computer program on the algorithm.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

Algorithm:

function linear_search(integer array[], integer n, integer x)
{
integer k;
for (k = 0, k < n, k++)
if (array [k] = x)
return k;
return -1;
}

Example to Implement Linear Search

The program code to implement a linear search is as given below. This program has been written in C programming. Let’s go through the following program to understand how it helps us find the requisite element in the list using the linear search algorithm. Study each and every component of the code properly, including the statements, variables, loops, etc.

Code:

#include <stdio.h>
#include <conio.h>
int linear_search(int arr[], int n, int x)
{
int i;
for(i = 0; i < n; i++)
if(arr[i] == x)
return i + 1;
return -1;
}
void main()
{
int arr[50], n, i, x, res;
printf("Enter the number of elements in array: ");
scanf("%d", &n);
printf("\nEnter the numbers: ");
for(i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("\nEnter the number to be searched: ");
scanf("%d", &x);
res = linear_search(arr, n, x);
if(res == -1)
printf("\n%d does not exist in the array.", x);
else
printf("\n%d is present at position %d in the array.", x, res);
getch();
}

Code Explanation: The above program first asks the user to specify the number of elements in the array along with the elements. It takes up to 50 elements. Once the array is specified, the user is asked to specify the element that needs to be searched in the array in the next step. The program using loop sequentially searches for the desired element. For this task, a function linear_search() has been used as seen in the code.

Popular Course in this category
All in One Data Science Bundle (360+ Courses, 50+ projects)360+ Online Courses | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (3,220 ratings)
Course Price

View Course

Related Courses
Oracle DBA Database Management System Training (2 Courses)SQL Training Program (7 Courses, 8+ Projects)

If the element is found in the array, then the function linear_search() returns the element’s position, and if the element is not found in the array, then -1 is returned. We must verify and validate the correctness of the implemented program. For this, the program should be checked by passing multiple parameters to it. We validate the program by passing multiple inputs. The inputs passed and the respective results obtained have been discussed in the below section.

Input 1

In this case, we decided to have ten elements in the array, and so, specified 10 when asked to specify the number of elements in the array. Next, we passed ten different numeric elements in the array. The inputs must be passed carefully. Passing input of different data types may give incorrect results. Also, while passing elements, they must be separated by space. Once, we pass the entire array correctly; next, we will specify the number that we intend to search in the array. Here, we want 98 to be searched. As 98 is present in the array, its position has been returned correctly by the program. So, the program worked correctly.

Linear Search in Data Structure in1

Input 2

In this case, we passed twenty-one elements into the array. Follow the steps and pass the inputs properly. After specifying the number of elements in the array, while passing the elements, ensure that the required number of elements are only passed. This is especially important when the number of elements in the array is high. Once done with the array, specify the requisite number to be searched. Here it is 29 as passed by us. 29 is present in the array, and the program successfully gave its position, which is 14. Go through the following output and see how the correct result has been obtained.

Linear Search in Data Structure in2

Input 3

Here, we passed eight three-digit numbers into the array. Then we specified number to be searched in the array, which is 245. As the number 245 is present in the list, so, the program correctly returned its position in the array. Go through the following program output. 

Linear Search in Data Structure in3

Input 4

Till now, we saw the program correctly returning the position of the element present in the array. However, the program should work correctly if the element is not present. The following program output shows this. As shown below, we decided to have eight elements in the array, and then specified the eight elements. After this, we specified the number to be searched, which is 102. 102 is not present in the array, and the program gave correct output saying that the number doesn’t exist in the array.

Linear Search in Data Structure in4

How Linear Search Algorithm Works

Let’s consider the following array to understand the working of the algorithm.

linear 1

Now, suppose we want to search 92 in the above-mentioned array, the linear search algorithm shall follow the steps mentioned below.

Step 1: The algorithm begins from the left-hand side, and the element to be searched is matched with every element. In the first, the matching doesn’t happen.

linear 2

Step 2: Now, the algorithm moves to the next element and compares the two elements to check if matching happens.

linear 3

Step 3: Similarly, the searching happens until no match happens.

linear 4

linear 5

Step 4: Finally, when the match happens, the algorithm returns the position of the element.

linear 6

Conclusion

Linear searches through a simple searching algorithm have vast applications. It is beneficial in situations that involve numerous elements. It is a straightforward methodology for searching requisite elements and can be implemented easily using any programming language.

Recommended Articles

This is a guide to Linear Search in Data Structure. Here we discuss the algorithm and working of Linear Search in Data Structure along with code implementation. You may also have a look at the following articles to learn more –

  1. How do Arrays work in Data Structure?
  2. Types of Data Analysis
  3. Different Types of Data Models
  4. Top Storages Devices
  5. How does Works B Tree in Data Structure?

All in One Data Science Bundle (360+ Courses, 50+ projects)

360+ Online Courses

1500+ Hours

Verifiable Certificates

Lifetime Access

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
Data Structures Tutorial
  • Basics
    • What is Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Asymptotic Analysis
    • Kruskal’s Algorithm
    • Prim’s Algorithm
    • BFS VS DFS
    • BCNF
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

Special Offer - All in One Data Science Bundle (360+ Courses, 50+ projects) Learn More