In that article, someone asked me about is there any other search algorithm exists? How can you search an element in the array if it's not sorted, and you cannot use the binary search algorithm? To answer his questions, I mentioned about the Linear search algorithm, which is the predecessor of binary search. Generally, it is taught before the binary search algorithm because the binary search is faster than Linear search. However, nevermind, you can still learn this useful algorithm to search an item in the array or linked list.
Linear search or sequential search is a method for finding a particular value in a list that consists of checking every one of its elements, one at a time and in sequence until the desired one is found.
The Linear search algorithm is the most straightforward. For a list of n items, the best case is when the value is equal to the first element of the list, in which case only one comparison is needed. The worst case is when the value is not in the list (or occurs only once at the end of the list), in which case n comparisons are needed.
The worst-case performance scenario for a linear search is that it has to loop through the entire collection, either because the item is the last one, or because the item is not found.
In other words, if you have N items in your collection, the worst-case scenario to find a topic is N iterations. In Big O Notation it is O(N). The speed of search grows linearly with the number of items within your collection. Unlike the Binary Search algorithm, Linear searches don't require the collection to be sorted.
Btw, if you are not familiar with the essential data structure and algorithms like this one, it's better to first go through a suitable data structure and algorithm course like
Data Structures and Algorithms: Deep Dive Using Java. This is a comprehensive resource to learn fundamental data structures and algorithms in Java programming languages. It's also very affordable, and you can buy in just $10 on Udemy's monthly sale.
Java Program to perform Linear Search
Here is our sample program to implement a sequential search algorithm in Java. It's self-explanatory, but if you have any doubt in understanding any part of the code then please shout and I would be happy to clear any doubt you have.
You can also read the
Grokking Algorithms book, one of my favorite books to learn fundamentals Data Structure and Algorithms. It has a whole chapter on the liner and binary search and here is a diagram which neatly explains the difference between linear and binary search algorithm.
You can see how the linear search algorithm because slower and slower as the size of the array or number of elements increases.
import java.util.Arrays;
import java.util.Scanner;
/**
* Java program to implement linear search algorithm in Java. It's also known as
* sequential search, because its sequentially search array for desired element.
* It's best case performance is O(1), when number is located at first index of
* array, in worst case it can take upto N array index access and N comparison.
* In Big O notation, time complexity of linear search is O(n), where n is
* number of elements in array.
*
* @author Javin
*/
public class LinearSearchDemo {
public static void main(String args[]) {
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
for (int number : primes) {
int index = linearSearch(primes, number);
if (index != -1) {
System.out.printf("'%d' is found at index '%d' %n", number,
index);
} else {
System.out.printf("'%d' not found in array %n", number,
Arrays.toString(primes));
}
}
}
/**
* Search a number in array using linear search algorithm. It's one of the
* simplest algorithm in programming world, which just require iterating
* over array and comparing each element with desired one. Once found you
* break the loop and return index of element.
*
* @param array
* @param number
* @return index of number in array, or -1 if not found
*/
public static int linearSearch(int[] array, int number) {
for (int i = 0; i < array.length; i++) {
if (array[i] == number) {
return i;
}
}
return -1; // Number not found in array
}
}
Output:
'2' is found at index '0'
'3' is found at index '1'
'5' is found at index '2'
'7' is found at index '3'
'11' is found at index '4'
'41' is found at index '12'
'43' is found at index '13'
'47' is found at index '14'
That's all about how to implement a linear search algorithm in Java. It is one of the first search algorithms you should learn in your computer science class. Teachers and Professors explain binary search next, but you have already learned that. Nevermind, we have a lot of sorting algorithms that you can explore after this, and the following article will help you.
Posts
