KnowledgeBoat Logo

Arrays

Linear Search

ICSE Computer Applications

Linear search is straightforward and simple. Let’s say this is our array and we want to check if 7 is present in the array or not.

In Linear Search, we start at the beginning of the array and check to see if the first element is the element, we are looking for. If it is, we are done. If it isn’t as is the case here, we move to next element in the list. We repeat this sequence until we have found our item, or we reach the end of the array and know that our element is not present in the array. In this case we found 7 at index 3 in the array in 4 steps. Remember that it took us 4 steps to find 7 in the array. We will come back to this point when we will discuss Binary Search and compare the number of steps needed in both the algorithms.

Linear Search Java Program

Let's look at the Java program for Linear Search in BlueJ and understand it’s working.

import java.util.Scanner;

public class LinearSearchDemo
{
   public static void main(String args[]) {

       Scanner in = new Scanner(System.in);
       int arr[] = {1, 8, 4, 7, 5};
       
       System.out.print("Enter number to search: ");
       int n = in.nextInt();
       
       int i = 0;
       for (i = 0; i < arr.length; i++) {
           if (arr[i] == n)
               break;
       }
       
       if (i < arr.length)
           System.out.println(n + " found at index " 
                                   + i + " in the array");
       else
           System.out.println(n + " not found in the array");
   }
}

In the main method of the program, after creating an object of Scanner class, we declare and initialize an int array — int arr[] = {1, 8, 4, 7, 5};. Next, we ask the user to enter a number that we will search in the array. We accept this number using the nextInt method of Scanner class.

//Linear Search Loop from above program
int i = 0;
for (i = 0; i < arr.length; i++) {
   if (arr[i] == n)
       break;
}

In the above loop of the program, we perform Linear Search to check if n is present in the array or not. We go over each element of the array and compare it with n. If we find a match, we know that the element is present in the array. There is no need to continue with the rest of the iterations of the loop, so we break out of the loop. Otherwise, we continue checking the remaining elements of the array.

if (i < arr.length)
   System.out.println(n + " found at index " 
                           + i + " in the array");
else
   System.out.println(n + " not found in the array");

In the code outside the loop (shown above), we check if i is less than the total number of elements present in the array. If this condition is true, it means that we found n in the array and exited the loop by executing the break statement. So i will contain the index of n in the array. If this condition is false, it means that we looked through all the elements of the array but didn’t find n, so n is not present in the array.

Here is the output of the program when we tried to search for 7 in the array:

BlueJ output of Linear Search Java program

After accepting the number from the user and initializing i to 0, program control comes to the for loop. In the first iteration, the first element of the array which is 1 is compared to 7. As they are not equal, the condition is false, break statement is not executed, and program control goes back to the beginning of the for loop. i is incremented to 1. As i is still less than 5, second iteration of the for loop starts. The second element of the array which is 8 is compared to 7. They are not equal, loop enters its third iteration. The third element of the array which is 4 is compared to 7. Not equal, 4th iteration begins. 4th element of the array is 7, it is equal to n so the condition becomes true and program control executes the break statement. Program control moves out of the loop to the if statement. The value of i is 3 and arr.length is 5 (the number of elements in the array). If condition is true. The println statement prints 7 found at index 3 in the array.

Now let’s see the case when the number is not present in the array. This time I am trying to find 6.

BlueJ output of unsuccessful Linear Search in Java

As you can see in the output above, the program correctly tells me that 6 was not found in the array.

That was Linear Search. As I said before, simple and straightforward isn’t it? Next, we will look at Binary Search.

PrevNext