In this article, we will learn in details about the Linear Search algorithm.
What is Linear Search?
In computer science, linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.
In this article, we will write code to do a linear search with different input like input can be ordered or unordered integer array.
- Unordered Linear Search
- Sorted/Ordered Linear Search
To know about binary search implementation, please click-here.
Unordered Linear Search
Let us assume we are given an array where the order of the elements is not known. That means the elements of the array are not sorted. In this case, to search for an element we have to scan the complete array and see if the element is there in the given list or not.
public class LinearSearch {
public static final int unorderedLinearSearch(int value, int[] array) {
for (int i = 0; i < array.length; i++) {
int iValue = array[i];
if (value == iValue)
return i;
}
return Integer.MAX_VALUE;
}
public static void main(String[] args) {
int[] integers = {1,2,3,4,5,6,7,8,8,8,9,9,9,0};
//the element that should be found
int shouldBeFound = 9;
int atIndex = LinearSearch.unorderedLinearSearch(shouldBeFound, integers);
System.out.println(String.format("Should be found: %d. Found %d at index %d. An array length %d"
, shouldBeFound, integers[atIndex], atIndex, integers.length));
}
}
Output:
search Key : 9. Found 9 at index 10. An array length 14
Time complexity: O(n), in the worst case we need to scan the complete array.
Space complexity: O(1).
Sorted/Ordered Linear Search
If the elements of the array are already sorted, then in many cases we don’t have to scan the complete array to see if the element is there in the given array or not. In the algorithm below, it can be seen that, at any point if the value at A[i] is greater than the data to be searched, then we just return –1 without searching the remaining array.
public class LinearSearch {
public static final int orderedLinearSearch(int value, int[] array) {
for (int i = 0; i < array.length; i++) {
if (value == array[i]){
return i;
}
else if (array[i] > value){
return -1;
}
}
return Integer.MAX_VALUE;
}
public static void main(String[] args) {
int[] sortedArray = {10,20,30,40,50};
//the element that should be found
int key = 30;
int atIndex = LinearSearch.orderedLinearSearch(key, sortedArray);
System.out.println(String.format("Should be found: %d. Found %d at index %d. An array length %d"
, key, sortedArray[atIndex], atIndex, sortedArray.length));
}
}
Output:
Should be found: 30. Found 30 at index 2. An array length 5
The time complexity of this algorithm is O(n). This is because in the worst case we need to scan the complete array. But in the average case, it reduces the complexity even though the growth rate is the same. Space complexity: O(1).
Note: For the above algorithm we can make further improvement by incrementing the index at a faster rate (say, 2). This will reduce the number of comparisons for searching in the sorted list.
Complete Program
/**
* In computer science, linear search or sequential search is a method for
* finding a target value within a list. It sequentially checks each element of
* the list for the target value until a match is
* found or until all the elements have been searched.
* <p>
* Worst-case performance O(n)<br>
* Best-case performance O(1)<br>
* Average performance O(n)<br>
* Worst-case space complexity O(1)<br>
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Linear_search">Linear Search (Wikipedia)</a>
* <br>
* @author Ramesh Fadatare
*/
public class LinearSearch {
public static final int unorderedLinearSearch(int value, int[] array) {
for (int i = 0; i < array.length; i++) {
int iValue = array[i];
if (value == iValue)
return i;
}
return Integer.MAX_VALUE;
}
public static final int orderedLinearSearch(int value, int[] array) {
for (int i = 0; i < array.length; i++) {
if (value == array[i]){
return i;
}
else if (array[i] > value){
return -1;
}
}
return Integer.MAX_VALUE;
}
public static void main(String[] args) {
int[] integers = {1,2,3,4,5,6,7,8,8,8,9,9,9,0};
//the element that should be found
int shouldBeFound = 9;
int atIndex = LinearSearch.unorderedLinearSearch(shouldBeFound, integers);
System.out.println(String.format("Should be found: %d. Found %d at index %d. An array length %d"
, shouldBeFound, integers[atIndex], atIndex, integers.length));
int[] sortedArray = {10,20,30,40,50};
//the element that should be found
int key = 30;
atIndex = LinearSearch.orderedLinearSearch(key, sortedArray);
System.out.println(String.format("Should be found: %d. Found %d at index %d. An array length %d"
, key, sortedArray[atIndex], atIndex, sortedArray.length));
}
}
Output:
Should be found: 9. Found 9 at index 10. An array length 14
Should be found: 30. Found 30 at index 2. An array length 5Master in DS and Algorithms on Data Structures and Algorithms in Java
Comments
Post a Comment