Question

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

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

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\\",
index, recursions, comparisons);
}
}

Answer 1

Below is the completed code that can for the binarySearch method, and it is made up of counting the number of calls to binarySearch() and the number of target comparisons:

Java

static public int binarySearch(int target, ArrayList integers,

int lower, int upper) {

static int recursions = 0; // Count recursive calls

static int comparisons = 0; // Count target comparisons

recursions++; // Increment recursion count

if (lower > upper) {

return -1; // Target not found

}

int mid = (lower + upper) / 2; // Calculate midpoint

comparisons++; // Count target comparison

if (target == integers.get(mid)) {

return mid; // Target found

} else if (target < integers.get(mid)) {

return binarySearch(target, integers, lower, mid - 1); // Search lower half

} else {

return binarySearch(target, integers, mid + 1, upper); // Search upper half

}

}

So, based on the above, in the main() method, one can be able to access the recursions as well as the comparisons variables like this:

Java

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

System.out.printf("index: %d, recursions: %d, comparisons: %d\\",

index, recursions, comparisons);