Computer Science, asked by zebamoid292, 23 days ago

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

Answered by yashrajgupta95
1

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.

Similar questions