The first part of this assignment is to modify the binary search algorithm such
ID: 3885515 • Letter: T
Question
The first part of this assignment is to modify the binary search algorithm such that the following conditions
are met:
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.
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
public class BinarySearch
{
/**
*Search the given array for the given integer using a binary
*search .This method assumes that the elements in the array
*are stored in order .if the element is found,the method
*returns the position of the element,otherwise it returns -1.<p>
*
*/
public static int binsearch(int[] array,int target)
{
int start = 0; //the start of the search region
int end = array.length - 1; //the end of the search region
int position = -1; //position of the target
//while there is still something list left to search and
//the element has not been found
while (start <= end && position == -1)
int mid = start + (end - start)/2;
// int mid = (start + end )/2; //Location of the middle
//Determine whether the target is smaller than ,greater than,
//or equal to the middle element
if(target < array[mid])
{
//Target is simaller; continue the left half end = mid - 1;
}
else if (target > array[mid])
{
//Target is larger,continue the right half end = mid + 1;
}
else
{
//Found it!
position = mid;
}
}
//return the location of the target
//could be -1 if not found
return position;
}
/**
*Search the given array for the given integer using a binary
*Search.This method assumes that the elaements in the array
*are stored in order.if the element is found, the method
*returns the positioin of the element ,otherwise it returns -1<p>
*
*@parm array the array of integers to search<p>
*@param target the integer to search for<p>
*
*@return targets position if found, -1 otherwise
*
*/
public static int binsearchRecursive(int[]array,int target,int start, int end)
{
int position = -1; //position of the target
if (start <=end)
{
int mid = start + (end - start)/2;
// int mid = (start + end)/2; //Location of the middle
//determine wether the target is smaller than,greater than,
//or equal to the middle element
if (target < array[mid])
{
//Target is smaller;continue the left half
position = binsearchRecursive(array ,target, satrt,mid - 1);
}
else if (target > array[mid])
{
//Target is larger,continue the right half
position = binsearchRecursive(array,target,start,mid +1,end);
}
else
{
//found it!
position = mid;
}
//Return the location of the target
//could be -1 if not found
return position;
}
/**
* the method <code> testBinarysearch<?code>tests the binary search method
*for an given array.we search the values at the boundary of the array
*as well as a non -exisisting value in the array.<p>
*
*@param numbers an <code>int[]</code>value which is the given array.<p>
*/
public static void testBinarySearch(int[] numbers)
{
system.out.println("search for 16,location should be at 4," +"found at " + binsearch (numbers,16));
system.out.println("search for 196,location should be at 14," +"found at " + binsearch (numbers,196));
system.out.println("search for 0,location should be at 0," +"found at " + binsearch (numbers,0));
system.out.println("search for 361,location should be at 19," +"found at " + binsearch (numbers,361));
system.out.println("search for 15,location should be at -1," +"found at " + binsearch (numbers,15));
}
/**
*use binary search to fimd a proper place to insert a new number.<p>
*the new number should be inserted after this location.<p>
*
*@param array the data collection
*@param target the new number to be inserted
*/
public static int binsearchForinsertion(int[] array,int target)
{
int start = 0; //the start of the search region
int end = array.lenght - 1; //the end of the search region
int position = -1; // position of the target
//while there is still something list left to search and
//the element has not been found
while (start <=end && position == -1)
int mid = start + (end - start)/2;
// int mid = (start + end)/2; //location of the middle
//determine wether the target is smaller than ,greater than ,
//or equal to the middle element
if(target <<array[mid])
{
//Target is smaller,continue the left half end = mid -1;
}
else if (target >array[mid])
{
//target is larger,continue the right half start = mid +1;
}
else
{
//found it!
position = mid;
}
}
if (position == -1)
{
position = start;
while (position <end && array[position] < target)
position ++;
position --;// insert after the position
}
}
return position;
}
/**
*method <code>testBoinsearchforinsertion</code> tests
*the binary search for inserti0n method
*for an given array.
*
*@param numbers an <code>int[]</code> value which is the given array.<p>
*/
public static void testbinarysearchforinsertion(int[] numbers)
{
system.out.println("search for 15,location should be at 3," +"found at " + binsearchForinsertion (numbers,15));
system.out.println("search for 197,location should be at 14," +"found at " + binsearchForinsertion (numbers,197));
system.out.println("search for 363,location should be at 19," +"found at " + binsearchForinsertion (numbers,363));
system.out.println("search for -1,location should be at -1," +"found at " + binsearchForinsertion (numbers,-1));
}
public static void main(string args[])
{
int size = 20;
int[] numbers = new int [size];
for(int i =0; i*i; i++)
numbers[i] = i*i;
system.out.println('testing binary search.. in the range (0-" +((size - 1)*(size - 1)) +")");
testBinarySearch(numbers);
system.out.println("/n=====================/n");
system.out.println("testing recursive binary search .. in the range (0 -"+((size -1) *(size -1)) +")");
testbinarySearch(numbers);
system.out.println("/n======================/n");
system.out.println('testing binary search.. in the range (0-" +((size - 1)*(size - 1)) +")");
testBinarySearch(numbers);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.