I need help finishing this code, and the directions are posted as comments withi
ID: 3754787 • Letter: I
Question
I need help finishing this code, and the directions are posted as comments within the code. You are not allowed to leave in the call to Arrays.sort() that we put in your starter file. That call is just to ensure that your insertInOrder is getting the correct index value to work with so you can debug your insertInOrder before you work on your binary search.
import java.util.*;
import java.io.*;
public class Project3
{
static final int INITIAL_CAPACITY = 5;
public static void main( String args[] ) throws Exception
{
if (args.length < 1 )
{
System.out.println("ERROR: Must enter an int on cmd line (i.e. # of random ints to put in array) ");
System.exit(0);
}
int numInts2generate = Integer.parseInt( args[0] );
// WE USE Random number generator to fill our array
Random randGen = new Random( 17 ); // SEED with 17
int[] arr = new int[INITIAL_CAPACITY];
int count= 0;
for ( int i = 0 ; i {
if ( count==arr.length ) arr = upSizeArr(arr);
insertInOrder( arr, count++, 1 + randGen.nextInt(1000) );
}
arr=trimArr(arr,count); // Now count == .length
printArray( arr ); // we trimmed it thus count == length so we don't bother to pass in count
} // END MAIN
// ############################################################################################################
static void printArray( int[] arr )
{
for( int i=0 ; i System.out.print(arr[i] + " " );
System.out.println();
}
static int[] upSizeArr( int[] fullArr )
{
int[] upSizedArr = new int[ fullArr.length * 2 ];
for ( int i=0; i upSizedArr[i] = fullArr[i];
return upSizedArr;
}
static int[] trimArr( int[] oldArr, int count )
{
int[] trimmedArr = new int[ count ];
for ( int i=0; i trimmedArr[i] = oldArr[i];
return trimmedArr;
}
// REMOVE ALL COMMENTS FROM INSERT IN ORDER JUST BEFORE HANDIN
static void insertInOrder( int[] arr, int count, int newVal )
{ // WAIT TILL YOUR PROGRAM PRODUCES CORRECT OUTPUT.
// THEN REPLACE THE LINE BELOW WITH A CALL TO -YOUR- BSEARCH
int index = Arrays.binarySearch( arr, 0, count, newVal );
//if index is negative, convert/decode back to non negative
// write a loop that opens up a slot at [index]
arr[index] = newVal; // LEAVE THIS HERE. DO NOT REMOVE
}
// REMOVE ALL COMMENTS FROM BSEARCH JUST BEFORE HANDIN
static int bSearch(int[] a, int count, int key)
{
return 0; // JUST TO MAKE IT COMPILE.
/* DEFINE & INITIALIZE LO, MID AND HI
while ( lo <= hi )
{
make your guess ( assign value into mid)
test your guess ( is arr[mid] less than, greater than or equal to key)
adjust the value of lo or hi according to the results of the test
}
IF YOU MAKE IT HERE, KEY IS -NOT- IN ARRAY
IN THAT CASE RETURN AN ENCODED FROM OF THE INDEX WHERE IT BELONGS
A NOT-FOUND KEY ALWAYS BELONGS AT INDEX LO.
return encoded form of low which is add one then negate
*/
}
} // END PROJECT3
Explanation / Answer
Below is your code: -
public class Project3 {
static final int INITIAL_CAPACITY = 5;
public static void main(String args[]) throws Exception {
if (args.length < 1) {
System.out.println("ERROR: Must enter an int on cmd line (i.e. # of random ints to put in array) ");
System.exit(0);
}
int numInts2generate = Integer.parseInt(args[0]);
// WE USE Random number generator to fill our array
Random randGen = new Random(17); // SEED with 17
int[] arr = new int[INITIAL_CAPACITY];
int count = 0;
for (int i = 0; i < numInts2generate; ++i) {
if (count == arr.length)
arr = upSizeArr(arr);
insertInOrder(arr, count++, 1 + randGen.nextInt(1000));
}
arr = trimArr(arr, count); // Now count == .length
printArray(arr); // we trimmed it thus count == length so we don't
// bother to pass in count
} // END MAIN
// ############################################################################################################
static void printArray(int[] arr) {
for (int i = 0; i < arr.length; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
static int[] upSizeArr(int[] fullArr) {
int[] upSizedArr = new int[fullArr.length * 2];
for (int i = 0; i < fullArr.length; ++i)
upSizedArr[i] = fullArr[i];
return upSizedArr;
}
static int[] trimArr(int[] oldArr, int count) {
int[] trimmedArr = new int[count];
for (int i = 0; i < count; ++i)
trimmedArr[i] = oldArr[i];
return trimmedArr;
}
// REMOVE ALL COMMENTS FROM INSERT IN ORDER JUST BEFORE HANDIN
static void insertInOrder(int[] arr, int count, int newVal) {
int binaryIndex = bSearch(arr, count, newVal);
int index = (-(binaryIndex)) - 1;
for (int i = arr.length - 1; i >= index; i--) {
if (i <= 0)
break;
arr[i] = arr[i - 1];
}
arr[index] = newVal; // LEAVE THIS HERE. DO NOT REMOVE
}
// REMOVE ALL COMMENTS FROM BSEARCH JUST BEFORE HANDIN
static int bSearch(int[] a, int count, int key) {
int high = count - 1;
int low = 0;
int mid = (high + low) / 2;
while (low <= high) {
if (key == a[mid]) {
return mid;
} else if (key < a[mid]) {
high = mid - 1;
mid = (high + low) / 2;
} else {
low = mid + 1;
mid = (high + low) / 2;
}
}
return -(low + 1);
}
} // END PROJECT3
Output
58 63 96 108 154 221 231 236 264 269 320 405 449 459 464 517 528 538 651 694 695 721 722 771 809 893 916 948 975 977
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.