Updated April 1, 2023
Introduction to Linear search in Java
Linear Search in Java is one of the simplest searching algorithms which helps to search for an element in the list in sequential order. But, linear search is rarely used as the other algorithms such as binary search algorithms, hash tables allow for faster search compared to linear search. Sequential search is performed for each item, i.e. every item is checked, and if there is a match found, then that item is returned; else, the search continues until the end of data collection. There are methods in Java to implement linear search operations. Let us dig deeper into this Linear Search and how it is implemented in Java in a stepwise manner with few examples.
Syntax
As there will be no Syntax available for Search Algorithms, there will be an Algorithm that will help us to implement Linear Search Algorithm in any Programming language.
Algorithm:
Step 1: First, we need to get the length of the array
Step 2: Get the element that has to be searched and store it in a variable
Step 3: Now, compare each element of the array with the searchable value
Step 4: If in case, there is a match. Then, the searchable element is found
Step 5: If not, i.e. if there is no match found. Then, the searchable element is not found and returns -1 if given
How to perform Linear Search Algorithm?
We will follow the above algorithmic steps to implement Linear Search Algorithm manually with an example and then get into programmatic examples.
Example:
Let Array A[4, 8, 2, 3, 6, 9]
Let searchable element X=3;
4 | 8 | 2 | 3 | 6 | 9 |
This is the array to be searched for X=3;
We need the length of the array when Linear Search is done Programmatically.
Starting from the first element
4 | 8 | 2 | 3 | 6 | 9 |
So Here X=3 = 4
Comparing with other elements
4 | 8 | 2 | 3 | 6 | 9 |
So here X=3 = 8
We, Will, move forward to the next element,
4 | 8 | 2 | 3 | 6 | 9 |
So here X=3 = 2
Will move forward,
4 | 8 | 2 | 3 | 6 | 9 |
So here X=3 = 3
Will return the index of the element and return. The index of the element is 3
If there was no element found until the end of the array, then it will return -1, i.e. not found.
Example #1
Linear Search Algorithm
class LinearSearchAlgorithm {
static int LSA(int array[], int length, int x)
{
for (int i = 0; i < length; i++) {
if (array[i] == x)
return i;
}
return -1;
}
public static void main(String[] args)
{
int[] array = { 4, 8, 2, 3, 6, 9 };
int length = array.length;
int x = 3;
int index = LSA(array, length, x);
if (index == -1)
System.out.println("Element not found in the array");
else
System.out.println("Element is found at index " + index);
}
}
Output:
Example #2
import java.util.Scanner;
class LSA
{
public static void main(String args[])
{
int length, k, i, array[];
Scanner input = new Scanner(System.in);
System.out.println("Enter length of the array:");
length = input.nextInt();
array = new int[length];
System.out.println("Enter " + length + " elements");
for (i = 0; i < length; i++)
{
array[i] = input.nextInt();
}
System.out.println("Enter the value to be searched:");
k = input.nextInt();
for (i = 0; i < length; i++)
{
if (array[i]== k)
{
System.out.println(k+" is found at index "+(i));
break;
}
}
if (i == length)
System.out.println(k + " is not found in the array");
}
}
Output 1:
Below are the inputs are given in the STDIN command prompt,
No. of array elements: 6
Array elements: 2, 4, 6, 8, 10, 1
Searchable value: 4
Output 2:
No. of array elements: 8
Array elements: 3, 5, 7, 9, 10, 34, 25, 21
Searchable value: 10
Output 3: If element not found
No. of elements: 5
Array elements: 2, 4, 5, 6, 10
Searchable value: 9
Time Complexity of Linear Search Algorithm
As the linear search algorithm is rarely used, other search algorithms such as hash tables and binary search allow fast search. The time complexity of Linear search is as follows:
If element is found in the array: O(n) to O(1)
If element is not found in the array: O(n) to O(n/2)
With this, we shall conclude our topic ‘Linear Search in Java’. We have seen what Linear Search Algorithm is and its implementation steps with an example. Also solved examples programmatically and showed various outputs, i.e. when the element is available and when the element is not available. Also seen the time complexity of the Linear Search Algorithm based on the searchable value if found or not. Thanks! Happy Learning!!
Recommended Articles
This is a guide to Linear search in Java. Here we discuss How to perform Linear Search Algorithm along with the examples and outputs. You may also have a look at the following articles to learn more –