Linear Search

Linear Search is the most primitive technique of searching for elements in a collection of data. This process goes step by step where every element of the list is checked starting from the top.

Algorithm

Suppose we have an array with the following elements: arr [] = {1, 5, 8, 9}
We want to search for the number 9.

A loop is run starting from the first index of the array until its length. An if statement checks whether the element at a particular index matches 9 or not.

We start with the first element which is 1. As it does not match with 9, the loop continues to iterate. Next in line, we have 5 and then 8. As neither match, we move on to the last element which is 9. As it matches the search element, the loop breaks off and the search has been successful.

Example and Code

class LinearSearch
{
public static int linSearch (int arr[] , int a)
for (int i = 0; i < n; i++)
{
if (arr[i] == a)
return i;
}
return -1;
}
public static void main (String args [])
{
int arr[] = {1, 2, 8, 10, 24, 7, 90, 55, 69, 100};
int a = 100;
int output = linSearch (arr , a);
if (output == -1)
System.out.println (“The element you are searching for is not present in the array”);
else
System.out.println (“The element” + a + “is present on the array in the index” + output);
}
}

OUTPUT

The element 10 is present on the array in index 9.

//If the value of variable a is changed to 109, the output will be as follows
The element you are searching for is not present in the array.

Complexity

The Time Complexity of Linear Search is of the order O(n). The worst-case in Linear Search is when the element being searched for is not present in the list. The best case, on the other hand, is when the element being searched for occurs as the first element on the list.