Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
12.18 LAB: Binary search Binary search can be implemented as a recursive algorithm. Each call makes a recursive call on one-half of the list the call received as an argument. Complete the recursive method binarySearch() with the following specifications: 1. Parameters: 。 a target integer 。 an ArrayList of integers 。 lower and upper bounds within which the recursive call will search 2. Return value: 。 the index within the ArrayList where the target is located 。 -1 if target is not found The template provides main() and a helper function that reads an ArrayList from input. The algorithm begins by choosing an index midway between the lower and upper bounds. 1. If target == integers.get(index) return index 2. If lower == upper, return -1 to indicate not found 3. Otherwise call the function recursively on half the ArrayList parameter: 。 If integers.get(index) < target, search the ArrayList from index + 1 to upper 。 If integers.get(index) > target, search the ArrayList from lower to index - 1 The ArrayList must be ordered, but duplicates are allowed. Once the search algorithm works correctly, add the following to binarySearch(): 4. Count the number of calls to binarySearch(). 5. Count the number of times when the target is compared to an element of the ArrayList. Note: lower Hint: Use a static variable to count calls and comparisons. The input of the program consists of: 1. the number of integers in the ArrayList 2. the integers in the ArrayList 3. the target to be located Ex: If the input is: == upper should not be counted. 9 1 2 3 4 56789 2 the output is: index: 1, recursions: 2, comparisons: 3

12.18 LAB: Binary search Binary search can be implemented as a recursive algorithm. Each call makes a recursive call on one-half of the list the call received as an argument. Complete the recursive method binarySearch() with the following specifications: 1. Parameters: 。 a target integer 。 an ArrayList of integers 。 lower and upper bounds within which the recursive call will search 2. Return value: 。 the index within the ArrayList where the target is located 。 -1 if target is not found The template provides main() and a helper function that reads an ArrayList from input. The algorithm begins by choosing an index midway between the lower and upper bounds. 1. If target == integers.get(index) return index 2. If lower == upper, return -1 to indicate not found 3. Otherwise call the function recursively on half the ArrayList parameter: 。 If integers.get(index) < target, search the ArrayList from index + 1 to upper 。 If integers.get(index) > target, search the ArrayList from lower to index - 1 The ArrayList must be ordered, but duplicates are allowed. Once the search algorithm works correctly, add the following to binarySearch(): 4. Count the number of calls to binarySearch(). 5. Count the number of times when the target is compared to an element of the ArrayList. Note: lower Hint: Use a static variable to count calls and comparisons. The input of the program consists of: 1. the number of integers in the ArrayList 2. the integers in the ArrayList 3. the target to be located Ex: If the input is: == upper should not be counted. 9 1 2 3 4 56789 2 the output is: index: 1, recursions: 2, comparisons: 3

Database System Concepts
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
icon
Related questions
Question

Write the full Java code for LabProgram.java

12.18 LAB: Binary search Binary search can be implemented as a recursive algorithm. Each call makes a recursive call on one-half of the list the call received as an argument. Complete the recursive method binarySearch() with the following specifications: 1. Parameters: 。 a target integer 。 an ArrayList of integers 。 lower and upper bounds within which the recursive call will search 2. Return value: 。 the index within the ArrayList where the target is located 。 -1 if target is not found The template provides main() and a helper function that reads an ArrayList from input. The algorithm begins by choosing an index midway between the lower and upper bounds. 1. If target == integers.get(index) return index 2. If lower == upper, return -1 to indicate not found 3. Otherwise call the function recursively on half the ArrayList parameter: 。 If integers.get(index) < target, search the ArrayList from index + 1 to upper 。 If integers.get(index) > target, search the ArrayList from lower to index - 1 The ArrayList must be ordered, but duplicates are allowed. Once the search algorithm works correctly, add the following to binarySearch(): 4. Count the number of calls to binarySearch(). 5. Count the number of times when the target is compared to an element of the ArrayList. Note: lower Hint: Use a static variable to count calls and comparisons. The input of the program consists of: 1. the number of integers in the ArrayList 2. the integers in the ArrayList 3. the target to be located Ex: If the input is: == upper should not be counted. 9 1 2 3 4 56789 2 the output is: index: 1, recursions: 2, comparisons: 3
Transcribed Image Text:12.18 LAB: Binary search Binary search can be implemented as a recursive algorithm. Each call makes a recursive call on one-half of the list the call received as an argument. Complete the recursive method binarySearch() with the following specifications: 1. Parameters: 。 a target integer 。 an ArrayList of integers 。 lower and upper bounds within which the recursive call will search 2. Return value: 。 the index within the ArrayList where the target is located 。 -1 if target is not found The template provides main() and a helper function that reads an ArrayList from input. The algorithm begins by choosing an index midway between the lower and upper bounds. 1. If target == integers.get(index) return index 2. If lower == upper, return -1 to indicate not found 3. Otherwise call the function recursively on half the ArrayList parameter: 。 If integers.get(index) < target, search the ArrayList from index + 1 to upper 。 If integers.get(index) > target, search the ArrayList from lower to index - 1 The ArrayList must be ordered, but duplicates are allowed. Once the search algorithm works correctly, add the following to binarySearch(): 4. Count the number of calls to binarySearch(). 5. Count the number of times when the target is compared to an element of the ArrayList. Note: lower Hint: Use a static variable to count calls and comparisons. The input of the program consists of: 1. the number of integers in the ArrayList 2. the integers in the ArrayList 3. the target to be located Ex: If the input is: == upper should not be counted. 9 1 2 3 4 56789 2 the output is: index: 1, recursions: 2, comparisons: 3
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Similar 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
SEE MORE TEXTBOOKS