# Java Array Tutorials
# Java Array Programs
➤ Find Length of Array
➤ Different ways to Print Array
➤ Sum of Array Elements
➤ Average of Array Elements
➤ Sum of Two Arrays Elements
➤ Compare Two Arrays in Java
➤ 2nd Largest Number in Array
➤ How to Sort an Array in Java
➤ Reverse an Array in Java
➤ GCD of N Numbers in Java
➤ Linear Search in Java
➤ Binary Search in Java
➤ Copy Array in Java
➤ Merge 2 Arrays in Java
➤ Merge two sorted Arrays
➤ Largest Number in Array
➤ Smallest Number in Array
➤ Remove Duplicates
➤ Insert at Specific Position
➤ Add Element to Array
➤ Remove Element From Array
➤ Count Repeated Elements
➤ More Array Programs
Java Matrix Programs
➤ Matrix Tutorial in Java
➤ Print 2D Array in Java
➤ Print a 3×3 Matrix
➤ Sum of Matrix Elements
➤ Sum of Diagonal Elements
➤ Row Sum – Column Sum
➤ Matrix Addition in Java
➤ Matrix Subtraction in Java
➤ Transpose of a Matrix in Java
➤ Matrix Multiplication in Java
➤ Menu-driven Matrix Operations
Linear Search or Sequential Search in Java | The Linear search or Sequential search is a method to find an element within a given list or array. Linear search or Sequential search is usually very simple to implement and is practical when the list has only a few elements, or when performing a single search in an unordered list.
Example:-
Array = {50, 90, 30, 70, 60};
Input to Search = 30
Output:- 30 found at Index 2.
Input to Search = 10
Output:- 10 not found.
How Linear Search Works?
In Linear search, finds the index or location of search in the given array. It begins the search by comparing the search key and the first element of the array/list. If the first element is not equal to the search key then it will compare with the next element, and so on until the match is found or the end of the array. If the match is found then it returns its index, else it will reach the end of the array or list which means the search key is not available.
Let us understand it through an example:- Given array = {50, 90, 30, 70, 60};
Assume the search key = 30; Then traverse through the array and compare with each element. The first element of the array is 50, but 50 is not equal to 30 therefore move to the next element. The next element is 90, but it is also not equal to 30 therefore move to the next element. The next element of the array is 30 which is equal to the search key 30, therefore, returns the index of the current element of the array.
It was the situation where the search key exists in the array, now let us assume when the search key is not available. Assume the search key = 10. Traverse through the array and compare with each element. It won’t match with 50, 90, 30, 70, 60, and finally reached the end of the array. Therefore return -1 which means the search key is not available.
Linear Search Algorithm in Java
The procedure to find an element in a given array or list through linear search,
a) Take array, size of the array, and the search key. Assume they are:- array, n, and key
b) Traverse through the array.
c) Compare the key with each element.
d) If the match is found then return the position.
e) Else repeat the process until the end of the array.
f) After traversing the array If the match is not found then return -1.
The algorithm for linear or sequential search can be given as,
linear search(array, n, key) {
i = 0;
while(i < n) {
if(key == array[i])
then return i;
else
i= i + 1;
}
return -1;
}The time complexity of the above algorithm:- O(n)
- Best-case performance:- O(1). When the search key is present at the first index/position of the array then only one comparison is required.
- Worst-case performance:- O(n). When the search key is present at the last index of the array then it requires N comparison, where N is the size of the array.
Linear Search Program in Java
Now let us develop a Java program to demonstrate the linear search algorithm. We will develop a method that will search the key in the given array using a linear search algorithm.
import java.util.Scanner;
public class Search {
public static void main(String[] args) {
// Scanner class object to read input
Scanner scan = new Scanner(System.in);
// array
int arr[] = { 50, 90, 30, 70, 60 };
// read search key
int key = 0;
System.out.print("Enter search key: ");
key = scan.nextInt();
// find size of array
int size = arr.length;
// linear search
int index = linearSearch(arr, size, key);
// display result
if (index == -1)
System.out.println(key + " not Found.");
else
System.out.println(key + " Found at Index = " + index);
// close Scanner class object
scan.close();
}
public static int linearSearch(int[] arr, int size, int key) {
// traverse through the array
for (int i = 0; i < size; i++) {
if (key == arr[i])
return i;
}
return -1;
}
}Output:-
Enter search key: 30
30 Found at Index = 2
Enter search key: 99
99 not Found.
Using Length Property to Search Array Element
In Java, every array has an in-built property to store the size of the array, and we can get it through the array.length therefore while developing methods in the Java programming language no need to pass the size of the array. Let us develop the same program without passing the size of the array.
import java.util.Scanner;
public class Search {
public static void main(String[] args) {
// Scanner class object to read input
Scanner scan = new Scanner(System.in);
// array
int arr[] = { 50, 90, 30, 70, 60 };
// read search key
int key = 0;
System.out.print("Enter search key: ");
key = scan.nextInt();
// linear search
int index = linearSearch(arr, key);
// display result
if (index == -1)
System.out.println(key + " not Found.");
else
System.out.println(key + " Found at Index = " + index);
// close Scanner class object
scan.close();
}
public static int linearSearch(int[] arr, int key) {
// traverse through the array
for (int i = 0; i < arr.length; i++) {
if (key == arr[i])
return i;
}
return -1;
}
}Linear Search for String Array in Java
Let us one more example using the String array in Java. Program description:- Write a Java program to find an element from a string array using the linear search or sequential search.
import java.util.Scanner;
public class Search {
public static void main(String[] args) {
// Scanner class object to read input
Scanner scan = new Scanner(System.in);
// array
String str[] = {"Java", "Python", "C++", "HTML", "CSS"};
// read search key
String key = null;
System.out.print("Enter search key: ");
key = scan.next();
// linear search
int index = linearSearch(str, key);
// display result
if (index == -1)
System.out.println(key + " not Found.");
else
System.out.println(key + " Found at Index = " + index);
// close Scanner class object
scan.close();
}
public static int linearSearch(String[] arr, String key) {
// traverse through the array
for (int i = 0; i < arr.length; i++) {
if (key.equals(arr[i]))
return i;
}
return -1;
}
}Output:-
Enter search key: Java
Java Found at Index = 0
Enter search key: HTML
HTML Found at Index = 3
Enter search key: Ruby
Ruby not Found.
Enter search key: Spring
Spring not Found.
Linear Search Using Recursion in Java
A method that contains a call to itself is called the method. A technique of defining the recursive method is called recursion. The recursive method allows us to divide the complex problem into identical single simple cases that can handle easily. This is also a well-known computer programming technique: divide and conquer.
import java.util.Scanner;
public class Search {
public static void main(String[] args) {
// Scanner class object to read input
Scanner scan = new Scanner(System.in);
// array
int arr[] = { 50, 90, 30, 70, 60 };
// read search key
int key = 0;
System.out.print("Enter search key: ");
key = scan.nextInt();
// linear search
int index = linear(arr, 0, key);
// display result
if (index == -1)
System.out.println(key + " not Found.");
else
System.out.println(key + " Found at Index = " + index);
// close Scanner class object
scan.close();
}
public static int linear(int arr[], int index, int key) {
if (index >= arr.length)
return -1;
else if (arr[index] == key)
return index;
else
return linear(arr, index + 1, key);
}
}Improved Version
We get worst-case performance O(n) because we are comparing array elements only from one side. Instead of one side, if we compare the array elements from both ends i.e. from the front and last then it will reduce the number of iterations. Let us understand it through an example,
Array = {10, 20, 30, 40, 50};
Search key = 40;
- In the first iteration, 40 is not equal to 10 (from the left side), and 40 is not equal to 50 (from the right side).
- In the second iteration, 40 is not equal to 20 (from the left side), but 40 is equal to 40.
- Therefore the search key is found at index 3.
The normal linear search can find it in 4 iterations, but an improved linear search can find it in only 2 iterations.
Java program for the above improved linear search,
import java.util.Scanner;
public class Search2 {
public static void main(String[] args) {
// Scanner class object to read input
Scanner scan = new Scanner(System.in);
// array
int arr[] = { 50, 90, 30, 70, 60 };
// read search key
int key = 0;
System.out.print("Enter search key: ");
key = scan.nextInt();
// linear search
int index = linearSearch(arr, key);
// display result
if (index == -1)
System.out.println(key + " not Found.");
else
System.out.println(key + " Found at Index = " + index);
// close Scanner class object
scan.close();
}
// Method for improved linear search
// if match found then return index of search key else return -1
public static int linearSearch(int arr[], int key) {
int n = arr.length;
for(int i=0, j=n-1; i<=n/2; i++, j--) {
if(key == arr[i])
return i;
if(key == arr[j])
return j;
}
return -1;
}
}Output:-
Enter search key: 70
70 Found at Index = 3
The best-case time complexity is the same as previous:- O(1)
The worst-case time complexity:- O(n/2)
Also See,
- Linear Search Algorithm in DSA
- C Program for Linear Search
- C++ Program for Linear Search
- Python Program for Linear Search
If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!