Answered: Write a Java program that implements…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Write a Java program that implements both Linear Search and Binary Search. The program will
take a collection of objects (generic type data) as input and print the number of comparisons needed
to find a target element within that collection.
You will create the following two Java classes:
1. SearchCombo.java : Code for both linearSearch and binarySearch will be in this class. You
may take help from the textbook Chapter 9, Section 9.1. However, note that the design require-
ments are different from the textbook code.
•Both search methods must use the Comparable<T> interface and the compareTo() method.
•Your program must be able to handle different data types, i.e., use generics.
•For binarySearch, if you decide to use a midpoint computation formula that is different from
the textbook, explain that formula briefly as a comment within your code.
2. Tester.java : This class will contain the main() method. The user will be asked to enter the
collection of elements (comma or space can be used to separate the elements). The output will
be the number of comparisons the two searching techniques require.
Review the sample output given below to get an idea of what the program output should look like.

Enter the elements (search pool):
1 12 18 22 31 34 40 46 59 67 85
Target:
40
# of comparisons for Linear Search: 4
# of comparisons for Binary Search: 2
Enter the elements (search pool):
1 12 18 22 31 34 40 46 59 67 85
Target:
100
Not found!
# of comparisons for Linear Search: 8
Not found!
# of comparisons for Binary Search:
5

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Follow-up Questions

Read through expert solutions to related follow-up questions below.

Follow-up Question

//From what I can tell, the answer provided does not answer my question. Asking again. Please read.

2. Tester.java : This class will contain the main() method. The user will be asked to enter the
collection of elements (comma or space can be used to separate the elements). The output will
be the number of comparisons the two searching techniques require.
Review the sample output given below to get an idea of what the program output should look like.
Your output may include additional information.

//need help making the tester class and improving the SearchCombo below

//SearchCombo.java

public class SearchCombo {
public static <T>
boolean linearSearch(T[] data, int min, int max, T target) {
int index = min;
boolean found = false;
while (!found && index <= max) {
found = data [index].equals(target);
index++;
}
return found;
}
public static <T extends Comparable<T>>
boolean binarySearch(T[] data, int min, int max, T target) {
boolean found = false;
int midpoint = (min + max)/2;
if (data[midpoint].compareTo(target)==0)
found = true;
else if(data[midpoint].compareTo(target)>0) {
if(min<=midpoint-1)
found = binarySearch(data, min, midpoint-1, target);
}
else if (midpoint+1<=max)
found=binarySearch(data, midpoint+1, max, target);
return found;
}
}

### Linear Search vs Binary Search Comparison

#### Example 1:
**Input:**
- **Elements (search pool):**
```
1 12 18 22 31 34 40 46 59 67 85
```
- **Target:**
```
40
```

**Output:**
- **# of comparisons for Linear Search:** 4
- **# of comparisons for Binary Search:** 2

#### Explanation:
1. **Linear Search**: Each element in the list is sequentially checked until the target is found. Here, it took 4 comparisons to find the target element 40.
2. **Binary Search**: The search interval is halved in each step. Here, it took only 2 comparisons to locate the target element 40.

---

#### Example 2:
**Input:**
- **Elements (search pool):**
```
1 12 18 22 31 34 40 46 59 67 85
```
- **Target:**
```
100
```

**Output:**
- **Not found!**
- **# of comparisons for Linear Search:** 8
- **Not found!**
- **# of comparisons for Binary Search:** 5

#### Explanation:
1. **Linear Search**: Each element in the list is sequentially checked until the end of the list is reached or the target is found. It took 8 comparisons to determine that the target element 100 is not in the list.
2. **Binary Search**: The search interval is halved in each step. It took 5 comparisons to determine that the target element 100 is not in the list.

### Summary
- **Linear Search**: Checks each element one by one, potentially examining all elements in the list.
- **Binary Search**: Efficiently narrows down the possible location of the target by halving the search interval with each comparison.

Binary Search is significantly faster for larger, sorted lists, demonstrating its efficiency compared to Linear Search.

Solution

by Bartleby Expert

SEE SOLUTION

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions