Linear Search in Java: Algorithm, Examples, and Implementation Guide

Linear search, sometimes called sequential search, is a basic searching algorithm used to find an element in a dataset such as an array or list. The main idea is simple: start at the beginning of the collection and check each element, one after another, until the desired value is found or the end of the dataset is reached.

Unlike more advanced algorithms like binary search, linear search does not require the data to be sorted. This makes it suitable for both sorted and unsorted datasets. Linear search is commonly used for small collections or when the order of data is unknown or irrelevant.

The algorithm is easy to understand and implement, making it a popular choice for beginners and for situations where simplicity is more important than efficiency. However, for large datasets, linear search can be slow because it may need to examine every element.

Typical use cases for linear search include:

• Searching for a specific value in a small list or array
• Looking up an item in an unsorted dataset
• Scenarios where the overhead of sorting or using complex algorithms is unnecessary

Linear search is a straightforward technique for finding a specific value within a collection, such as an array or list. Its working principle is based on a simple, step-by-step process: examine each element in order, compare it to the target value, and stop as soon as a match is found.

Step-by-Step Algorithm

The linear search algorithm operates as follows:

1. Start at the Beginning
   Begin with the first element in the collection (at index 0).
2. Compare Each Element
   Check if the current element matches the target value you are searching for.
3. Check for a Match
   
   • If the element matches the target, the search ends, and the index (position) of the element is returned.
   • If it does not match, move to the next element in the collection.
4. Continue Sequentially
   Repeat the comparison for each subsequent element, moving one by one through the collection.
5. End Condition
   If you reach the end of the collection without finding the target, return -1 (or a similar indicator) to show that the element is not present.

This process is called "linear" because it checks elements in a straight, sequential line, without skipping or making assumptions about their order.

How the Method Operates

• Unconditional Traversal: Linear search does not require the data to be sorted. Every element is checked, regardless of its value or position.
• Early Termination: The search stops immediately once the target element is found—no unnecessary comparisons are performed after a match.
• Exhaustive Search: If the target is not present, every element is checked exactly once.

Example Walkthrough

Suppose you have an array:
[4, 9, 2, 7, 5]
You want to find the value 7.

• Compare 4 (index 0) to 7 → no match.
• Compare 9 (index 1) to 7 → no match.
• Compare 2 (index 2) to 7 → no match.
• Compare 7 (index 3) to 7 → match found! The search stops, and index 3 is returned.

If the target value (for example, 6) is not present, the algorithm checks each element and, after reaching the end, returns -1.

Applicability

Linear search can be implemented using loops (iterative) or recursion (recursive), but the fundamental working principle remains the same: check each element, one at a time, until a match is found or the collection ends.

Explanation of Linear Search (With Pseudocode)

Linear Search in Java systematically goes through the list, checking each value against the one you’re looking for. If found, it returns the index. Otherwise, it returns -1 if the search completes without a match. 

Pseudocode:

function findValue(list, valueToFind):
    for position from 0 to list.length - 1:
        if list[position] == valueToFind:
            return position
    return -1

Example:

Suppose you have the array [4, 9, 2, 7, 5], and you want to find 7.

• Start at index 0 → 4 → no match
• Index 1 → 9 → no match
• Index 2 → 2 → no match
• Index 3 → 7 → match found!

Since 7 is located at index 3, the function returns 3. If the number wasn’t in the list, the function would return -1 to show that it couldn’t find the value.

How Does Linear Search in Java Work?

Linear search is one of the simplest searching techniques. It works by checking each element of a list one by one until the required value is found or the list ends.

Let us understand this with a simple example.

Step 1: Understand the Input

Suppose we have the following list of numbers:

[2, 4, 0, 1, 9]

And we want to find the number:

k = 1

Here:

• The list contains the elements to be searched.
• k is the target value.
• The search always starts from the first element (index 0).

At this stage, the algorithm is ready to begin comparing elements.

Step 2: Start Checking from the First Element

The linear search algorithm begins from the first element of the array and compares it with the target value k.

The comparisons happen one by one:

• Is 2 equal to 1? No
• Is 4 equal to 1? No
• Is 0 equal to 1? No
• Is 1 equal to 1? Yes

After every comparison, if the element does not match, the algorithm moves to the next position.

Only one element is checked at a time.

Step 3: Stop When the Element Is Found

When the algorithm reaches the value 1, it matches the target k.

At this point:

• The search stops.
• The position of the element is returned.

In this example, 1 is found at index 3.

No further comparisons are needed after a match is found.

Step 4: What If the Element Is Not Present?

If the target value does not exist in the list, the algorithm will continue checking until the last element.

Example:

k = 7
Array = [2, 4, 0, 1, 9]

Search process:

• All elements are compared.
• No match is found.
• The end of the list is reached.

In this case, the algorithm returns:

-1

The value -1 indicates that the element is not present in the array.

Some programs may also display a message like “Element not found”.

Step 5: Basic Java Logic of Linear Search

The main logic of linear search in Java looks like this:

for(int i = 0; i < arr.length; i++) {
    if(arr[i] == k) {
        return i;   // Element found
    }
}
return -1;          // Element not found

Explanation:

• The loop starts from index 0.
• Each element is compared with k.
• If a match is found, the index is returned.
• If the loop finishes without a match, -1 is returned.

This simple loop is the core of linear search.

Step 6: Complete Working Flow of Linear Search

The working process of linear search can be summarized as follows:

1. Take the input array and target value.
2. Start from the first element.
3. Compare the current element with the target.
4. If they match, return the index and stop.
5. If they do not match, move to the next element.
6. Repeat until the end of the array.
7. If no match is found, return -1.

This process continues in a straight, sequential manner.

Time and Space Complexity

• Best case: When the element is at the first position.
• Worst case: When the element is at the last position or not present.
• Space complexity: O(1), since no extra memory is used.

Key Features of Linear Search

• Works on both sorted and unsorted arrays.
• Does not require any special preparation.
• Easy to understand and implement.
• Suitable for small datasets.
• Slower for large datasets.

Note

Linear search is the most basic searching technique in programming. It helps beginners understand how searching works at a fundamental level.

Although it is not efficient for large data, it is very useful for small programs, simple applications, and learning purposes. Once you master linear search, it becomes easier to understand advanced searching methods like binary search.

1. Using Loops

You can implement Linear Search in Java by using a simple for loop to check each element one after another.

Java Code For Linear Search:

public class LinearSearchExample {
    public static int findElement(int[] data, int target) {
        for (int index = 0; index < data.length; index++) {
            if (data[index] == target) {
                return index;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] numbers = {10, 5, 3, 8, 6};
        int valueToFind = 8;
        int position = findElement(numbers, valueToFind);

        if (position != -1) {
            System.out.println("Element found at index: " + position);
        } else {
            System.out.println("Element not found");
        }
    }
}

Code Explanation:

The function in this Java program for linear search checks each element sequentially; if it matches the target, it returns the index, otherwise, it returns -1 after checking the entire array.

Output:

Element found at index: 3

Time and Space Complexity:

• Time Complexity: O(n), because, in the worst case, it examines every element.
• Space Complexity: O(1), because it uses only a few variables for iteration.

2. Using Recursion

You can also implement Linear Search in Java recursively by calling the method again with the next index.

Java Code For Linear Search:

public class LinearSearchRecursive {
    public static int searchRecursive(int[] data, int target, int index) {
        if (index == data.length) {
            return -1;
        }
        if (data[index] == target) {
            return index;
        }
        return searchRecursive(data, target, index + 1);
    }

    public static void main(String[] args) {
        int[] numbers = {2, 4, 0, 1, 9};
        int valueToFind = 1;
        int position = searchRecursive(numbers, valueToFind, 0);

        if (position != -1) {
            System.out.println("Element found at index: " + position);
        } else {
            System.out.println("Element not found");
        }
    }
}

Code Explanation:

The function checks one element and then recursively checks the next. In a Java program for linear search, if it finds the value, it returns the index. If it reaches the end without a match, it returns -1.

Output:

Element found at index: 3

Time and Space Complexity:

• Time Complexity: O(n), since each element is checked once.
• Space Complexity: O(n), because each recursive call adds a frame to the call stack.

3. Without Using a Function

You can also perform a linear search in Java directly inside the main method without creating a separate function.

Java Code For Linear Search:

public class LinearSearchWithoutFunction {
    public static void main(String[] args) {
        int[] numbers = {2, 4, 0, 1, 9};
        int valueToFind = 1;
        boolean found = false;

        for (int index = 0; index < numbers.length; index++) {
            if (numbers[index] == valueToFind) {
                System.out.println("Element found at index: " + index);
                found = true;
                break;
            }
        }

        if (!found) {
            System.out.println("Element not found");
        }
    }
}

Code Explanation:

Here, the loop directly checks each element and prints the index if a match is found. If not, it notifies the user that the element was not found, just like a typical Java program for linear search would do.

Output:

Element found at index: 3

Time and Space Complexity:

• Time Complexity: O(n), sequential checking.
• Space Complexity: O(1), minimal extra memory usage.

Quick Recap

• Linear search can be implemented using loops, recursion, or directly in the main method.
• All methods check elements one by one from start to end.
• The loop-based method is the most efficient and commonly used.
• The recursive method uses extra memory due to function calls.
• Direct implementation is suitable for small and simple programs.

When analyzing the efficiency of linear search, two main factors are considered: time complexity and space complexity.

Time Complexity

• Best Case:
  The best-case scenario occurs when the target element is located at the very beginning of the collection. In this case, linear search makes only one comparison, so the time complexity is O(1).
• Worst Case:
  The worst-case scenario happens when the target element is either at the very end of the collection or not present at all. In both situations, every element must be checked, resulting in O(n) comparisons, where n is the number of elements in the dataset.
• Average Case:
  On average, the target element might be located somewhere in the middle of the collection. Statistically, this means about half of the elements will be checked, but the time complexity is still considered O(n).

Space Complexity

• Iterative Approach:
  Linear search implemented with a loop uses only a small, constant amount of extra memory (for variables like the index and the target), regardless of the size of the dataset. Therefore, the space complexity is O(1).
• Recursive Approach:
  If linear search is implemented recursively, each recursive call adds a new layer to the call stack. In the worst case (target not found), there will be n recursive calls, leading to a space complexity of O(n).

Summary Table

Properly handling edge cases ensures that linear search works reliably across different scenarios, especially when dealing with unsorted arrays or unexpected input. Here are some important cases and how to address them:

1. Empty Array

If the array is empty, there are no elements to check. The algorithm should immediately return a value (such as -1) to indicate that the number is not present in the array.

2. Number Not Present in the Array

If the search completes a single pass through the entire array without finding the target value, the algorithm should return -1 or another indicator. This signals that the element is not present in the collection.

3. Multiple Occurrences

When the target value appears more than once in an unsorted array, linear search returns the index of the first matching value it encounters. If all occurrences are needed, the algorithm must be modified to collect every index.

4. Single Element Array

If the array contains only one element, the algorithm checks that single value. If it matches the target, it returns index 0; otherwise, it returns -1.

5. Unsorted Arrays

Linear search works on unsorted arrays, making a single pass from start to end. It does not require sorting or any special data arrangement.

Error Handling Best Practices

• Always check for empty or null arrays before starting the search to avoid runtime errors.
• Use a consistent return value (such as -1) to indicate that the element was not found, making it easy to handle in calling code.
• Clearly document the behavior when multiple occurrences exist—by default, only the first matching value is returned.

Summary

Handling edge cases and errors is essential for writing strong and reliable linear search programs.

By properly managing empty arrays, missing values, multiple matches, invalid input, and performance issues, you can ensure that your searching technique works correctly in real-world situations.

Good error handling turns simple algorithms into professional-quality solutions.

Linear Search and Binary Search are two commonly used searching techniques in programming. Both are used to find an element in a list, but they work in very different ways and are suitable for different situations.

Understanding their differences helps you choose the right method based on data size and arrangement.

Java sequential search is simply another name for Linear Search. It checks each element in order until the target value is located.

Sequential Search Java Code Example:

public class SequentialSearchExample {
    public static int sequentialSearch(int[] data, int target) {
        for (int i = 0; i < data.length; i++) {
            if (data[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] numbers = {2, 4, 0, 1, 9};
        int valueToFind = 1;
        int position = sequentialSearch(numbers, valueToFind);

        if (position != -1) {
            System.out.println("Element found at index: " + position);
        } else {
            System.out.println("Element not found");
        }
    }
}

Code Explanation:

The sequentialSearch method iterates through the given array, comparing each element to the target value. If a match is found, it returns the index where the element occurs. If the loop completes without finding the value, it returns -1, indicating absence. The Java sequential search method shows this by searching for a specific number and printing the result.

Output:

Element found at index: 3

Time and Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

• Unsorted data: This method works well even if the data hasn’t been sorted in any specific order, which saves time when dealing with raw or incoming data.
• Small to medium-sized lists: For datasets that aren’t too large, linear search performs efficiently enough without needing complex algorithms.
• When simplicity matters: Ideal for cases where easy-to-understand code is more important than execution speed, such as beginner-level projects or quick utility programs.

Real-Life Examples:

• Finding a person’s name in a small contact list on your phone.
• Checking whether a specific word is present in a paragraph of text.
• Searching for a student's roll number in a class attendance register.

Linear Search in Java is the simplest way to understand how searching works in programming. By checking elements one by one, it clearly demonstrates the core idea of comparing data to find a match.

While it is not the fastest option for large datasets, linear search is extremely valuable for small or unsorted data and for building strong fundamentals. Mastering this algorithm helps beginners develop logical thinking and prepares them to confidently learn advanced searching techniques like binary search and hashing.

In short, linear search may be basic, but it is a crucial first step toward becoming a skilled programmer.

Points to Remember 

1. Linear search always checks elements sequentially. It starts from the first index and moves forward without skipping any value.
2. No sorting is required before searching. Unlike binary search, linear search works on both sorted and unsorted arrays.
3. Performance depends on element position. The closer the target is to the beginning, the faster the search completes.
4. Iterative implementation is more memory-efficient. Loop-based linear search uses constant space, while recursion uses extra stack memory.
5. Linear search builds the foundation for advanced algorithms. Understanding this method makes it easier to learn binary search, hash tables, and indexing techniques.

1. What is sequential search, and is it the same as linear search?

Yes, sequential search is another term for linear search. Both refer to the searching technique where each element in an array is checked one by one in a linear fashion until the target element is found or the end is reached.

2. Can I use linear search on any type of array?

Absolutely. Linear search works on arrays containing numbers, strings, or objects. The key is to use the correct comparison operation for the element type.

3. How does linear search work with the Scanner class in Java?

You can use the Scanner class to read user input (such as the target element) and then perform a linear search on the array to find if the element exists.

4. What happens if the element is not present in the array?

If the element is not found after checking all array elements in a linear fashion, the algorithm returns -1 or a similar value to indicate the element is missing.

5. Is linear search suitable for large datasets?

Linear search is not efficient for large datasets because it may require checking every element. For large, sorted datasets, consider using more advanced searching algorithms.

6. Does linear search require the array to be sorted?

No, linear search works on both sorted and unsorted arrays. Sorting is not necessary for this searching technique.

7. What is the main advantage of linear search?

Its main advantage is simplicity. It is easy to implement and understand, making it suitable for small datasets or quick checks.

8. Will linear search always find all occurrences of an element?

No, standard linear search returns the index of the first matching value found in the array. If you need all occurrences, you must modify the algorithm.