The process of looking for a particular element in an array is called searching an array in java.
Searching means checking whether an element (value) is present in an array or not. The value can be anything such as character, number, string, etc.
Searching is the most common task in the data processing. Many algorithms and data structures are dedicated to searching.
Arrays class provides two searching approaches that are as follows:
- Linear Search
- Binary Search
In this tutorial, we will concentrate on linear search algorithm in java with example programs. In the next tutorial, we will discuss the binary search algorithm.
Linear Array Search Algorithm in Java
Linear search means sequential search. A linear search algorithm (or approach) is probably very simple and easy to implement.
For given a search element, the algorithm examines all elements of an array for equality until it finds a match or reaches the end.
The searching systematically begins with the starting position of an array i.e. 0th index and continues to search the element one after another until the element has been found.
Once the element is found, the linear search returns the index location. If the search element is not found, the linear search will return -1.
In other simple words, the linear search technique successively compares the key with each element in the array.
Does key == x[0]?
Does key == x[1]?
Does key == x[2]? etc.
This process continues to do so until the key matches an element in the array or the array is ended without a match being found. If a match is found, the search terminates and returns the index of the element in the array that matches the key.
If no match is found, the search returns -1 or some other value indicating a failure to locate key. This approach is called linear or sequential array search in java.
A linear search algorithm is a very slow process in java. It can be applied for both sorted and unsorted arrays. In the case of sorted array, the binary search algorithm is better than linear search algorithm.
Example Program based on Linear Search Algorithm
Let’s take a very simple example program where we will create an array of 10 integer values and examine whether a value 20 is present in it or not. Look at the systematic source code to understand better.
Program code:
package arraysProgram;
public class LinearSearchExample {
public static void main(String[ ] args)
{
int[ ] numbers = {2, 15, 30, 5, 6, 20, 8, 10, 9, 1};
int num = 20, flag = 0;
for(int i = 0; i < 10; i++)
{
if(numbers[i] == num)
{
flag = 1;
break;
}
}
if(flag == 1)
System.out.println("Number "+num+ " found successfully in the array.");
else
System.out.println("Number not found in the array.");
}
}
Output:
Number 20 found successfully in the array.
Reasons to use a variable flag in the program?
1. flag = 0: In this above program, we have created a variable flag and initialize it with 0 by default. This is because, while executing the program we are supposing that there is no search made and hence no matching element has been found.
2. flag = 1: This condition has been written for the interpreter to understand that the examining condition between the array and element (variable num) has been satisfied and the element has been found in the array.
Why we have used the break statement in the program?
we know that break is a keyword used to terminate the loop or even program, depending on where we placed it. In the above program, we have used a break statement inside the if condition to terminate the loop.
This is because when the linear search finds a search element in the array, it is unnecessary to go through the whole loop.
2. Let’s create another linear search program where we will take all the inputs from the user and will find the index location of a search element.
In this program, we will use the Scanner class to take the inputs from the keyboard. You can also use InputStreamReader and BufferedReader classes to take input from the user.
Program code:
package arraysProgram;
import java.util.Scanner;
public class LinearSearchExample {
public static void main(String[ ] args)
{
// Create an object of Scanner class with System.in.
Scanner sc = new Scanner(System.in);
int[ ] numbers = new int[10];
int num, flag = 0, iLoc = 1;
System.out.println("Enter your 10 numbers in an array: ");
for(int i = 0; i < 10; i++)
{
numbers[i] = sc.nextInt();
}
System.out.println("Enter a number that has to be searched: ");
num = sc.nextInt();
for(int j = 0; j < 10; j++)
{
if(numbers[j] == num)
{
// Finding the index location of a search element.
flag = 1;
iLoc = iLoc + j;
break;
}
}
if(flag == 1)
System.out.println("Number "+num+ " found successfully at a index location " +iLoc);
else
System.out.println("Number not found");
}
}
Output:
Enter your 10 numbers in an array:
20 30 15 10 2 5 40 60 100 45
Enter a number that has to be searched:
45
Number 45 found successfully at a index location 10
The execution time of a linear search increases linearly as the number of elements in an array increases. Therefore, the linear search is inefficient for a large array.
Hope that this tutorial has covered almost all the important points concerning linear array search in java with various example programs. I hope that you will have understood the basic points of linear search algorithm in Java.
In the next tutorial, we will concentrate on the binary search algorithm that is better than linear search when an array has been already sorted in ascending order.
Thanks for reading!!!
Next ⇒ Binary Search in Java for Sorted Array⇐ Prev Next ⇒