8.12 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: Parameters: a target integer an ArrayList of integers lower and upper bounds within which the recursive call will search 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. If target == integers.get(index) return index If lower == upper, return -1 to indicate not found 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(): Count the number of calls to binarySearch(). Count the number of times when the target is compared to an element of the ArrayList. Note: lower == upper should not be counted. Hint: Use a static variable to count calls and comparisons. The input of the program consists of: the number of integers in the ArrayList the integers in the ArrayList the target to be located   Starter code for LabProgram.java   import java.util.Scanner; import java.util.ArrayList; import java.util.Collections; public class LabProgram {    // Read and return an ArrayList of integers.    private static ArrayList readNums(Scanner scnr) {       int size = scnr.nextInt();                // Read size of ArrayList       ArrayList nums = new ArrayList();       for (int i = 0; i < size; ++i) {          // Read the numbers          nums.add(scnr.nextInt());       }       return nums;    }    static public int binarySearch(int target, ArrayList integers,                                     int lower, int upper) {       /* Type your code here. */    }    public static void main(String [] args) {       Scanner scnr = new Scanner(System.in);       // Input a list of integers       ArrayList integers = readNums(scnr);       // Input a target value for the search       int target = scnr.nextInt();       int index = binarySearch(target, integers, 0, integers.size() - 1);       System.out.printf("index: %d, recursions: %d, comparisons: %d\n",                         index, recursions, comparisons);    } }

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
icon
Concept explainers
Question

8.12 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():

  1. Count the number of calls to binarySearch().
  2. Count the number of times when the target is compared to an element of the ArrayList. Note: lower == upper should not be counted.

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

 

Starter code for LabProgram.java

 

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class LabProgram {
   // Read and return an ArrayList of integers.
   private static ArrayList<Integer> readNums(Scanner scnr) {
      int size = scnr.nextInt();                // Read size of ArrayList
      ArrayList<Integer> nums = new ArrayList<Integer>();
      for (int i = 0; i < size; ++i) {          // Read the numbers
         nums.add(scnr.nextInt());
      }
      return nums;
   }

   static public int binarySearch(int target, ArrayList<Integer> integers,
                                    int lower, int upper) {
      /* Type your code here. */
   }

   public static void main(String [] args) {
      Scanner scnr = new Scanner(System.in);
      // Input a list of integers
      ArrayList<Integer> integers = readNums(scnr);

      // Input a target value for the search
      int target = scnr.nextInt();

      int index = binarySearch(target, integers, 0, integers.size() - 1);

      System.out.printf("index: %d, recursions: %d, comparisons: %d\n",
                        index, recursions, comparisons);
   }
}

Ex: If the input is:
9
1 2 3 4 5 6 7 8 9
2
the output is:
index: 1, recursions: 2, comparisons: 3
Transcribed Image Text:Ex: If the input is: 9 1 2 3 4 5 6 7 8 9 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 4 steps with 4 images

Blurred answer
Knowledge Booster
Types of Linked List
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