For this problem I had to modify a binary search algorithm to meet the follow co
ID: 3886238 • Letter: F
Question
For this problem I had to modify a binary search algorithm to meet the follow conditions:
1. The algorithm returns an index where a specified item should be inserted such that the
ordering of all items will be preserved after the insertion has occurred. Note that we are not
concerned here with performing the actual insertion, only with returning the insertion point.
2. The algorithm should always return a non-negative integer regardless of whether or not
the item to be inserted is already in the array. Again, since we are not concerned with
performing the actual insertion, it is acceptable for the algorithm to return an index that is
greater than the current length of the array. It will be assumed that some other method will
handle any array resizing and item shifting. In other words, assume someone else will be
writing an insert method that is responsible for actually inserting items into an array. This
method would call your modified binarySearch algorithm to get the correct insertion index,
and then insert the item.
3. Your algorithm must use Comparable objects. Do not write the algorithm so that it only
works with primitive data values such as int or double. If you want to use integers or
primitive data, use the built-in wrapper classes (Integer, Double, Long, Float, Character,
Byte, etc.). These wrapper classes already implement the Comparable interface, so they are
Comparable objects. Java’s autoboxing feature will automatically convert a primitive data
value to the appropriate wrapper type, eliminating the hassle of manually instantiating
wrapper objects. For example, you can create an array of Integer objects by typing:
Integer[] intArray = {1, 2, 3, 4, 5, 6};.
(One cautionary note: keep in mind that characters and character strings are compared
using ASCII codes, which means, for example, that an upper case ‘Z’ is considered to be
less than a lower case ‘a’.)
4. I will test your code by pasting your modified method in my own test harness. Be sure to
remove all debugging code from your method, and make sure your method does not need
to call other methods or reference any global variables in order to work.
This is the code I have:
import java.io.*;
public class BinarySearch
{
public int binarySearch(Comparable[] objArray, Comparable searchObj)
{
int low = 0;
int high = objArray.length - 1;
int mid = 0;
while (low <= high)
{
mid = (low + high) / 2;
if (objArray[mid].toString().toLowerCase().compareTo(searchObj.toString().toLowerCase()) < 0)
//compatibility
{
low = mid + 1;
}
else if (objArray[mid].toString().toLowerCase().compareTo(searchObj.toString().toLowerCase()) > 0)
//compatibility
{
high = mid - 1;
}
else
{
return mid;
}
}
if(objArray[mid].toString().toLowerCase().compareTo(searchObj.toString().toLowerCase()) > 0)
return mid;
else
return mid +1;
}
public static void main (String[]args) {
Integer[] intArray = {1,3,5,6};
int index;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print(" Enter a number to insert or to search for: ");
Integer obj;
try {
obj = Integer.parseInt(br.readLine());
BinarySearch bs = new BinarySearch();
index = bs.binarySearch(intArray, obj);
System.out.println(" Index where number: "+ obj + " is found or should be inserted = "+index);
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
}
I am not sure how to handle the next part:
Testing Your Implementation
By now, I’m sure everyone is aware of the importance of testing code, but because this particular assignment
lends itself well to being an exercise in test case generation—since the test cases for this problem
can be easily elucidated—we will incorporate test case creation as part of the assignment. There are 3
conditions that need to be tested that are related to the positioning of the item being inserted:
1. the lower boundary of the array
2. the upper boundary of the array
3. between the upper and lower boundaries of the array
For each of the three conditions there are two possibilities:
1. the item already exists in the array
2. the item does not exist in the array
Furthermore, the array may contain:
1. an odd number of items, or
2. an even number of items.
The combinations of the above factors yield a total of 3 * 2 * 2, or 12 test categories, assuming the array
is not empty. The empty array yields a 13th test category, which should also be tested.
To test your code, do the following:
1. Create a set of 13 test cases, one test case for each of the 13 test categories described
above. Recall that every test case should consist of 1) inputs and 2) expected output. Each
test case should consist of an array of Comparable objects and an object of the same type
to be inserted into the array, as inputs, and the correct insertion point for the item to be
inserted, as the expected output. You can create your tests using jUnit or some other
testing library, or you can create your own test harness. A test harness is simply a program
that passes the inputs of test cases to the code to be tested, and checks the actual output
against the expected output. The results are displayed on the screen or written to a testing
log file.
2. With your test cases in hand, test your modified binarySearch method.
Explanation / Answer
binary search method has modified
import java.io.*;
public class BinarySearch
{
public int binarySearch(Comparable[] objArray, Comparable searchObj)
{
int low = 0;
int high = objArray.length - 1;
int mid = 0;
while (low <= high)
{
mid = (low + high) / 2;
if (objArray[mid].toString().toLowerCase().compareTo(searchObj.toString().toLowerCase()) < 0)
//compatibility
{
low = mid + 1;
}
else if (objArray[mid].toString().toLowerCase().compareTo(searchObj.toString().toLowerCase()) > 0)
//compatibility
{
high = mid - 1;
}
else
{
return mid;
}
}
if(objArray[mid].toString().toLowerCase().compareTo(searchObj.toString().toLowerCase()) > 0)
return mid;
else
return mid +1;
}
public static void main (String[]args) {
Integer[] intArray = {1,3,5,6};
int index;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print(" Enter a number to insert or to search for: ");
Integer obj;
try {
obj = Integer.parseInt(br.readLine());
BinarySearch bs = new BinarySearch();
index = bs.binarySearch(intArray, obj);
System.out.println(" Index where number: "+ obj + " is found or should be inserted = "+index);
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.