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,
Let us understand linear search with the help of an example,
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.
(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.
- If found then return true.
- If Not found after searching till then return false.
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.
Post a Comment