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 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.

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
icon
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
Transcribed Image Text: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

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps

Blurred answer
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.
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.
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.
Transcribed Image Text:### 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
Bartleby Expert
SEE SOLUTION
Knowledge Booster
Developing computer interface
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
  • SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education