Java Program for Linear Search.

Java Program for Linear Search.

---

Linear search is a searching algorithm which sequentially searches element in an array.

In this algorithm, elements of array is scanned one by one and check if it is matching with element to search and if found return true else return false.

In last post, we saw how to do Binary search: Binary Search in Java. In this post, we will focus on linear serach.

Lets understand the problem statement graphically and it will be more clear,  

Linear Search Algorithm

---

Let us understand linear search with the help of an example,

You might be familiar with the audio casette tape containing songs as shown below 
(it is rarely used now).

Audio casette tape works in sequence, that is if there are 5 songs in it and you want to listen third song then you can't directly jump to third song and have to go through first and second song to reach third song.You have to pass by each song one by one till end. 
Linear seach works very similar to audio casette tape.

In linear search, for searching any element in an array, we have to start from begining, scanning each element of the array till end to see match found.

1. If found then return true. 
2. If Not found after searching till then return false.

See the below example that will give more idea on How Linear Search Algorithm works.

Linear Search Time Complexity

---

In last post, we saw how to do Binary search: Binary Search in Java. In this post, we will focus on linear serach.

In Linear search algorithm, in worst case, we need to visit all the elements of the array atleast once to see if the element is present or not. 

Example: 
Case 1: If I tell you to search 23 in array [6, 9, 2, 1, 18, 15, 40, 23]
You need to first compare 23 with arr[0] (6), then with arr[1] (9), then with arr[2] (2) and so on till we encounter 23 which is present at last. 

Case 2: If I tell you to search 14 in array [6, 9, 2, 1, 18, 15, 40, 23]
You need to first compare 14 with arr[0] (6), then with arr[1] (9), then with arr[2] (2) and so on till last element 23 to see 14 is present in array, in this case it is not present.

So from this, we can say that in worst case, we end up looking all the element of the array to check whether element to search is present or not.
Time Complexity of linear search algorithm is O(n) that is if there are n elements in array then we need to check "n" times.

Java Program for Linear Search.

---

package javabypatel;

public class LinearSearch {

 public static void main(String a[]){

  int[] arr = {12, 5, 10, 15, 31, 20, 25, 2, 40};
  int dataToSearch = 40;
  
  boolean isFound = search(arr, dataToSearch);
  if(isFound){
   System.out.println("Match found");
  }else{
   System.out.println("Match Not found");
  }
 }

 public static boolean search(int[] arr, int dataToSearch){
  for(int i=0; i<arr.length; i++){
   if(arr[i] == dataToSearch){
    return true;
   }
  }
  return false;
 }
}

You may also like to see

---

Binary Search in Java.

---

Transpose of M*N Matrix in Java

Count zeros in a row wise and column wise sorted matrix

Find Largest and Smallest number in Array

Find middle element of a linked list

Union and Intersection of Two Sorted Arrays

Merge two sorted arrays in Java

How is ambiguous overloaded method call resolved in java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.