Linear search or a sequential search is a method used to find an element in a list or an array. It searches for the element sequentially i.e. one after other until the required element is found.
Algorithm:
- Input the no. of elements in which the number has to be searched.
- Now, read the list of elements.
- Input the element to search for.
- Using a loop, search for the element in the list of elements.
- Exit loop. Stop.
Pseudo Code:
Input number of elements to variable n
Declare array, arr, that takes elements to it.
for i<-1 to n do
input the elements to the array.
end for
input element to be searched to k
for j<-1 to n do
if(arr[j]==k) then
break the loop.
end if.
end for
print the index at which the element is found.
Code in Java:
/* File Name: LinearSearch.java */
import java.util.*;
class LinearSearch{
public static void main(String[] args) {
int n,count=0,j;
try{
Scanner s=new Scanner(System.in);
System.out.print("Enter the number of elements in the array: ");
n=s.nextInt();
int []arr= new int[n];
System.out.println("Enter the elements: ");
for(int i=0;i<n;i++)
arr[i]=s.nextInt();
System.out.println("Enter the element to search for:");
int k=s.nextInt();
for(j=0;j<n;j++){
count+=1;
if(arr[j]==k)
break;
}
}
finally{
s.close();
}
System.out.println("Number is found at position: " + (j+1));
System.out.println("No. of iterations: "+ count);
}
Time Complexity:
Best case: When the element is found at the first index: O(1)
Worst case: Since the traversal should be the whole array in case the element searched exists at the end. So, the time complexity of the worst case is O(n).
Average case: When the time complexity is taken on larger scale i.e. with more number of inputs, then the average case would be O(n). The case will not be n/2 as this will not make much difference in the complexity as that would be higher as well.
Contributions in the comments!
Techprodezza 
5 thoughts on “Linear Search”