analysis.txt,TernarySearcher.java,TernarySearchTester.javaIn this lab, you'll analyze the ternary search algorithm, learn about a new testing strategy, and use the testing strategy to identify a bug in the provided code.
Please start by sharing with your lab partner through VS Code live share!
Do not open TernarySearcher.java until you reach the final part of the assignment!
Today, we are going to focus on a search algorithm called ternary search. Ternary search is similar to binary search, but we will use two midpoints. We will check both midpoints to determine if they match our target value. There are then three sub-arrays that may be searched depending on the result. That’s about all that you need to know to understand the algorithm since you already are familiar with binary search, but please ask questions if you have them!
Consider the following array to start:
| A | B | C | D | E |
Which indices should our two midpoints be set to such that after checking them, we’ll split our array evenly?
Now, discuss the runtime of the algorithm with your partner. Consider additional example arrays if you are unsure, and answer the following questions:
Please submit a file called analysis.txt containing your two midpoint indices and your answers to the three questions above alongside your code.
Now, you will implement a testing strategy sometimes known as “property-based testing”.1 This is an example of a standard test case you might have written before starting this lab:
We call the function and will look at the output to determine whether or not it matches the expected value (2). This approach works, but you might miss certain cases!
In the property-based testing strategy, you will instead repeatedly generate random inputs to your program to determine if any expected properties are not satisfied. In this case, we’ll generate random sorted arrays of numbers and confirm that our code always returns the index of each number in the array (the property). We’ll also make sure that if a number isn’t in the array, we return -1.
If you’d like a metaphor, this is like smacking the wall with a fly swatter thousands to times to see if you hit any bugs. Luckily, computers are better at doing repetitive things thousands of times than us humans!
This assignment comes with some starter code, but I have not provided you with the main class that you will write, TernarySearchTester.java. This is so that you get some more practice writing a class from scratch! To begin, create TernarySearchTester.java with a public class and a PSVM (main method). Add a quick print statement to your PSVM to make sure it runs before continuing.
Add the code provided below to your TernarySearchTester class and read it to make sure you understand it. You’ll have to add some imports; you can use the yellow lightbulb in VS code if you find it helpful.
Use generateExample to generate and print out one example in your main method.
public static int[] generateExample(int maxExampleLength, int maxVal) {
Random rng = new Random();
int exampleLength = rng.nextInt(1, maxExampleLength + 1);
int[] example = new int[exampleLength];
for (int j = 0; j < exampleLength; j++) {
example[j] = rng.nextInt(maxVal + 1);
}
Arrays.sort(example);
return example;
}This method first determines the length of the example between 1 and maxExampleLength. Then, it picks random numbers between 0 and maxVal and puts them in an array. Finally, it sorts the array.
Your main task is to write a method test that generates examples until it finds one that does not satisfy an expected property (or hits the maxExamples threshold).
test should be public, static, and return a FailedTestResult. It should have four integer parameters, in this order:
maxExamples in the code below)randomNumbers in the code below)The following is a skeleton for what the body of your method will look like:
for (int i = 0; i < maxExamples; i++) {
// TODO: replace the following line with a call that generates an example
// array
int[] example = new int[0];
// Test Type #1: check that -1 is returned when searching for an element
// within the range of values in the array that is not there
// build list of options for numbers within range that aren't in the array
ArrayList<Integer> choices = new ArrayList<>();
for (int j = example[0] + 1; j < example[example.length - 1]; j++) {
if (Arrays.binarySearch(example, j) < 0) {
choices.add(j);
}
}
// shuffle the options so that they are in random order for the next step
Collections.shuffle(choices);
// test the choices
for (int j = 0; j < randomNumbers && j < choices.size(); j++) {
int resultIndex = TernarySearcher.ternarySearch(choices.get(j), example);
// return a FailedTestResult object if the correct index is not returned
if (resultIndex != -1) {
return new FailedTestResult(example, choices.get(j), resultIndex);
}
}
// Test Type #2: check that when a value is outside of the range of the array (less than the
// lowest value or greater than the highest value), -1 is returned
// TODO: implement. You are only expected to test one value below and one value above the range
// Test Type #3: check that the correct index is returned for every element in the array
// TODO: implement
}
return null;I’ve implemented one test for you as an example, which tests that -1 is returned by ternarySearch when the target value is within the range of the sorted array but is not present. You should write the method signature, copy the skeleton above (once again, add imports as needed), and fill in all of the TODOs. The TODO first requires a call to generateExample. The second and third TODOs require testing ternarySearch and returning a FailedTestResult if an expected property is not satisfied.
As you complete the final TODO, make sure to account for the case where there are duplicate values in your array! Consider the following example
The output could be any value from 1 to 3 and be correct! Still, don’t over-think it. My implementation of this required one loop and six lines of code (including closing curly braces).
Call test in your PSVM and print out the resulting FailedTestResult. If it is not null, that implies that a test failed and there is a bug in ternarySearch. If you are seeing null, try different arguments to test (e.g., run more tests) and ensure that you followed the instructions for part 2 (there is a bug)!
Now, find and fix the bug in the ternarySearch implementation. I suggest calling TernarySearcher.ternarySearch with the example from your FailedTestResult. Walk through the code in the debugger and identify why you are getting the wrong result. Once you’ve fixed the bug, run ternarySearch again to confirm that the result is null. Note that the result being null doesn’t tell us that there is definitely no bug, it just tells us our code didn’t fail to satisfy any of the properties on any of the randomly generated inputs. Accordingly, you should make the maximum number of tests fairly large!
Once your result is null when you run many tests, you’re ready to submit! Your grade will be based on (a) your responses to the analysis questions, (b) your implementation of the property-based testing strategy, and (c) your bugfix.
You may find this testing strategy helpful on some other assignments as well!↩︎