In lecture we discussed the binary search algorithm which searches a sorted array for a key and returns either the index of where it was found, or if not found, returns the index of where it belongs. In such a case this belongs index is encoded as a negative number to distinguish it from being confused with a found index. The encoding is as follows: add 1 to index then negate. In lecture we also discussed the insertInOrder algorithm which reads a sequence of values from a source ( text file) and inserts them into an array keeping them sorted as each value is added to the array. For this project you will get your input from a random number generator. YOu will use your bSearch to determine where that number belongs in the array, then the insertInOrder code will write a loop to open up a slot for that element and put the value into the array. THe call to bSearch will figure out where the new key belongs in O(Log2N), where as a linear scan will take O(N). Using a binary search instead of a simple linear scan to figure out where the new key goes is an optimization of the insertInOrder algorithm. When the insertInOrder gets the index back from the binary search, it must examine that value to see if it is negative. If so, it must be decoded back to a real index. The decoding is actually the same operation: add one then negate it (back to positive).

/* Project3.java InsertInOrder with bSearch optimization to compute insertion index */

// STUDENT STARTER FILE

// YOUR NAME/ID:

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)\n");

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 )

{

// WAIT TILL YUR PROGRAM PRODUCES 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 whici is add one then negate

*/

}

} // END PROJECT3