Java Program for Linear Search

By the end of this session,you will learn what is linear search,use of linear search,algorithm and program for linear search.This is one of the important concept from Data Structure through java. Here, Searching means checking and finding an elements from list of elements. This means we can find out that element in the list or not.In fact, there are two standard searching techniques: they are Linear Search and Binary Search. In this session we will learn about Linear Search after this we shall learn Binary Search.

Linear Search or Sequential Search:

In this method, each element of an array is read one by one sequentially and it is compared with desired element. This method can be applied to a sorted or unsorted  list. A search will be unsuccessful if all the elements are read and the desired element is not found.

When to use Linear Search:

There are some fastest searching(Binary Search) methods,those requires that data must be sorted. What if data is unsorted? By that time we have to use simple searching technique called Linear Search. It finds a given number simply by compared with desire element.

Let us now try to understand this with the help of example which is an unsorted array.

In the above array figure consists of ten numbers. Here,if you want search 56 number,then 56 is compared with all the elements starting with 0th element and searching process ends when 56 is found or the list ends.

Example:

class Searching
{
public static void main(String args[])
{
int i,n;
int[] arr={49,12,34,23,56,2,29,42,48,11};
boolean found;
n=48;// number to find
System.out.println("the input data is fallows");
System.out.println("49,12,34,23,56,2,29,42,48,11");
System.out.println("The number to be searched:" +n);
found=false;
for(i=0;i<10;i++)
{
System.out.println("checking"+i+"th number = "+arr[i]);
{
if(arr[i]==n)
{
found=true;
break;
}
}
}
if(found)
System.out.println("the number is found");
else
System.out.println("the number is Not found");
return;
}

}

Output:

Algorithm:

Linear Search(a[],ele)
Step 1: Start
Step 2: set i=0,flag=1
Step 3: Repeat the steps 4,5  for loop (or) you can also use while loop
Step  4: if(a[i]==ele) then print i and flag=0
Step 5:i=i+1
Step 6: if(flag) then print element not found
Step 7: stop

TIME COMPLEXITY:

Time Complexity of the linear search is found by number of comparisons made in searching record.

Best Case:  The desired element is present in the first position of the array that means only one comparison is made,so f(n)=O(1)

Average Case: In this case,the desired element is found in the half position of the array,then
f(n)=O[(n+1)/2]

Worst case: The desired element is present in the nth position of the array that means last position,then f(n)=O(n+1)