Write a program in Java to input 15 integers in an array and an integer item, from the keyboard. Search the integer 'item' in the array using linear search technique and print the index of the item if found in the array otherwise print a message " item not found".
Answers
Answer:
Search Algorithms in Java
Chandan Singh
Introduction
Searching is one of the most common actions performed in regular business applications. This involves fetching some data stored in data structures like Arrays, List, Map, etc. More often than not, this search operation determines the responsiveness of the application for the end-user.
In this article, let's take a look at some of the searching strategies that can be used to cater to different scenarios. We will also implement them in Java and analyze their performance with some well-known parameters like Time and Space Complexity.
Linear Search
Binary Search
Knuth Morris Pratt Pattern Search
Jump Search
Interpolation Search
Exponential Search
Fibonacci Search
Java Collections API
Linear Search
Linear or Sequential Search is the simplest of search algorithms. While it most certainly is the simplest, it's most definitely not the most common, due to its inefficiency. It's a brute-force algorithm. Very rarely is it used in production, and in most cases, it's outperformed by other algorithms.
Linear Search has no pre-requisites for the state of the underlying data structure.
Explanation
Linear Search involves sequential searching for an element in the given data structure until either the element is found or the end of the structure is reached.
If the element is found, we usually just return its position in the data structure. If not, we usually return -1.
Implementation
Now let's see how to implement Linear Search in Java:
public static int linearSearch(int arr[], int elementToSearch) {
for (int index = 0; index < arr.length; index++) {
if (arr[index] == elementToSearch)
return index;
}
return -1;
}
To test it, we'll use a simple Array of integers:
int index = linearSearch(new int[]{89, 57, 91, 47, 95, 3, 27, 22, 67, 99}, 67);
print(67, index);
With a simple helper method to print the result:
public static void print(int elementToSearch, int index) {
if (index == -1){
System.out.println(elementToSearch + " not found.");
}
else {
System.out.println(elementToSearch + " found at index: " + index);
}
}
Output:
67 found at index: 8
Time Complexity
Here we are iterating through the entire set of N elements sequentially to get the location of the element being searched. The worst case for this algorithm will be if the element we are searching for is the last element in the array.
In this case, we will iterate N times before we find the element.
Hence, the Time Complexity of Linear search is O(N).
Space Complexity
This type of search requires only a single unit of memory to store the element being searched. This is not relevant to the size of the input Array.