Introduction

Searching is one of the most fundamental operations in computer programming. Whenever you search for a contact in your phone, look for a student’s name in a class list, or search for a product in a small inventory, you are performing a search operation.

One of the simplest searching algorithms is Linear Search.

Linear Search checks every element one by one until the desired element is found or the list ends. Because of its simplicity, it is one of the first searching algorithms every programmer should learn.

In this blog, we’ll explore Linear Search in detail with examples, Java programs, dry runs, time complexity analysis, and interview questions.

What is Linear Search?

Linear Search is a searching technique where each element of the array is checked sequentially until the target element is found.

It starts from the first element and compares each element with the value being searched.

If the element is found, its position is returned.

If the end of the array is reached without finding the element, the search is unsuccessful.

Real-Life Example

Imagine you are searching for a student named Rahul in an attendance register.

Aman
Karan
Priya
Rahul
Neha

You check:

Aman → Not Rahul
Karan → Not Rahul
Priya → Not Rahul
Rahul → Found!

This is exactly how Linear Search works.

How Linear Search Works

Suppose the array is:

Index : 0   1   2   3   4   5
Value : 12  45  23  89  50  67

Search for 89.

Step 1

12 == 89 ?
No

Step 2

45 == 89 ?
No

Step 3

23 == 89 ?
No

Step 4

89 == 89 ?
Yes

Element found at Index 3.

Algorithm

Start from the first element.
Compare the current element with the target.
If equal, return the index.
Otherwise move to the next element.
Repeat until the last element.
If not found, return -1.

Flowchart (Concept)

Start
   |
Read Array
   |
Read Target
   |
i = 0
   |
Is i < n ?
   |
Compare arr[i] with target
   |
Yes -------------> Found
 |
No
 |
i++
 |
Repeat
 |
Not Found
 |
Stop

Java Program – Linear Search

public class LinearSearch {

    public static void main(String[] args) {

        int[] numbers = {12, 45, 23, 89, 50, 67};

        int target = 89;

        int position = -1;

        for(int i = 0; i < numbers.length; i++) {

            if(numbers[i] == target) {
                position = i;
                break;
            }
        }

        if(position != -1)
            System.out.println("Element Found at Index " + position);
        else
            System.out.println("Element Not Found");
    }
}

Output

Element Found at Index 3

Program Explanation

int[] numbers = {12,45,23,89,50,67};

Creates an integer array.

int target = 89;

Element to search.

int position = -1;

Initially assume the element is not found.

for(int i=0;i<numbers.length;i++)

Loop through every element.

if(numbers[i]==target)

Compare current element with the target.

position=i;
break;

Store index and stop searching.

if(position!=-1)

Print the position if found.

Otherwise print “Not Found”.

Dry Run Example

Array:

{8, 12, 15, 20, 30}

Search = 20

Iteration	Index	Element	Comparison	Result
1	0	8	8==20	No
2	1	12	12==20	No
3	2	15	15==20	No
4	3	20	20==20	Found

Answer:

Index = 3

Example 2

Search for 30

Comparisons made:

Total comparisons = 5

Example 3

Search for 100

Comparisons

Reached the end.

Output

Element Not Found

Searching Strings

Linear Search can also search strings.

public class SearchName {

    public static void main(String[] args) {

        String[] names = {
                "Amit",
                "Rahul",
                "Priya",
                "Sneha",
                "Neha"
        };

        String search = "Sneha";

        boolean found = false;

        for(int i=0;i<names.length;i++) {

            if(names[i].equals(search)) {
                System.out.println("Found at Index " + i);
                found = true;
                break;
            }
        }

        if(!found)
            System.out.println("Name Not Found");
    }
}

Output

Found at Index 3

Searching Characters

public class CharacterSearch {

    public static void main(String[] args) {

        char[] letters = {'A','B','C','D','E'};

        char target = 'D';

        for(int i=0;i<letters.length;i++) {

            if(letters[i]==target) {

                System.out.println("Character Found at Index " + i);
                break;
            }
        }
    }
}

Output

Character Found at Index 3

Finding Maximum Using Linear Search

Although called “search”, the same sequential traversal helps find the maximum element.

public class MaximumElement {

    public static void main(String[] args) {

        int[] arr = {45,12,89,34,90,11};

        int max = arr[0];

        for(int i=1;i<arr.length;i++) {

            if(arr[i] > max)
                max = arr[i];
        }

        System.out.println("Maximum = " + max);
    }
}

Output

Maximum = 90

Finding Minimum Element

public class MinimumElement {

    public static void main(String[] args) {

        int[] arr = {45,12,89,34,90,11};

        int min = arr[0];

        for(int i=1;i<arr.length;i++) {

            if(arr[i] < min)
                min = arr[i];
        }

        System.out.println("Minimum = " + min);
    }
}

Output

Minimum = 11

Counting Occurrences

public class CountOccurrence {

    public static void main(String[] args) {

        int[] arr = {10,20,30,20,50,20};

        int target = 20;

        int count = 0;

        for(int i=0;i<arr.length;i++) {

            if(arr[i]==target)
                count++;
        }

        System.out.println("Occurrences = " + count);
    }
}

Output

Occurrences = 3

Searching Multiple Times

Suppose the array is

10 25 30 45 60

Searching

25 → Found

100 → Not Found

60 → Found

Each search starts again from index 0.

Time Complexity Analysis

The efficiency of an algorithm is measured using Time Complexity.

Best Case

The element is found at the first position.

Array

50 20 30 40 60

Search = 50

Comparisons

Time Complexity

O(1)

Average Case

The element is somewhere in the middle.

Example

10 20 30 40 50

Search = 30

Comparisons

Average Time Complexity

O(n)

Worst Case

The element is either the last element or not present.

Example

10 20 30 40 50

Search = 100

Comparisons

Worst Time Complexity

O(n)

Space Complexity

Linear Search does not require any extra memory.

Only a few variables are used.

Space Complexity = O(1)

Advantages of Linear Search

Very easy to understand.
Easy to implement.
Works on both sorted and unsorted arrays.
No preprocessing required.
Suitable for small datasets.
Can search arrays, strings, and lists.

Disadvantages of Linear Search

Slow for large datasets.
Checks every element sequentially.
Inefficient when repeated searches are required.
Much slower than Binary Search on sorted data.

Linear Search vs Binary Search

Feature	Linear Search	Binary Search
Array Required	Sorted or Unsorted	Must be Sorted
Method	Sequential Search	Divide and Conquer
Best Case	O(1)	O(1)
Average Case	O(n)	O(log n)
Worst Case	O(n)	O(log n)
Easy to Implement	Yes	Moderate
Suitable for Small Data	Yes	Yes
Suitable for Large Data	No	Yes

Applications of Linear Search

Linear Search is commonly used in:

Searching contacts in a small phonebook.
Searching student names in attendance.
Finding products in a small inventory.
Searching menu items in simple applications.
Checking duplicates in small arrays.
Searching values in unsorted data.
Searching through logs or records.

Common Mistakes Beginners Make

1. Forgetting the break statement

Without break, the loop continues even after finding the element.

2. Using == for String comparison

Incorrect

if(name == search)

Correct

if(name.equals(search))

3. Loop Boundary Error

Incorrect

i <= arr.length

Correct

i < arr.length

Using <= causes an ArrayIndexOutOfBoundsException.

4. Not Handling “Not Found”

Always initialize the position variable to -1 or use a boolean flag to indicate that the element was not found.

Interview Questions

1. What is Linear Search?

A sequential searching algorithm that checks each element one by one until the target is found or the array ends.

2. Does Linear Search require a sorted array?

No. It works on both sorted and unsorted arrays.

3. What is the Worst Case Time Complexity?

O(n)

4. What is the Best Case Time Complexity?

O(1)

5. What is the Space Complexity?

O(1)

6. When should Linear Search be preferred?

Small datasets.
Unsorted data.
One-time searches.
Simple applications.

Practice Programs

Try solving these on your own:

Search an integer in an array.
Search a student’s name in an array of strings.
Count the number of occurrences of an element.
Find the first occurrence of an element.
Find the last occurrence of an element.
Search a character in a character array.
Search a number entered by the user.
Find the maximum element using traversal.
Find the minimum element.
Search all occurrences of an element and print their indices.

Summary

Linear Search is the simplest searching algorithm and an excellent starting point for beginners learning Data Structures and Algorithms. It examines each element one by one until the desired element is found or the array ends. Although it is not the fastest algorithm for large datasets, it is easy to implement, works on both sorted and unsorted arrays, and requires only constant extra memory. Understanding Linear Search builds a strong foundation for learning more advanced algorithms such as Binary Search, Hashing, and Tree-based searching techniques.

Introduction

What is Linear Search?

Real-Life Example

How Linear Search Works

Algorithm

Flowchart (Concept)

Java Program – Linear Search

Output

Program Explanation

Dry Run Example

Example 2

Example 3

Searching Strings

Searching Characters

Finding Maximum Using Linear Search

Finding Minimum Element

Counting Occurrences

Searching Multiple Times

Time Complexity Analysis

Best Case

Average Case

Worst Case

Space Complexity

Advantages of Linear Search

Disadvantages of Linear Search

Linear Search vs Binary Search

Applications of Linear Search

Common Mistakes Beginners Make

1. Forgetting the break statement

2. Using == for String comparison

3. Loop Boundary Error

4. Not Handling “Not Found”

Interview Questions

1. What is Linear Search?

2. Does Linear Search require a sorted array?

3. What is the Worst Case Time Complexity?

4. What is the Best Case Time Complexity?

5. What is the Space Complexity?

6. When should Linear Search be preferred?

Practice Programs

Summary

Comments

Leave a Reply Cancel reply