Starter Code

/* Project4.java InsertInOrder with bSearch optimization to compute insertion index */ // STUDENT STARTER FILE // YOUR NAME/ID: import java.util.*; import java.io.*; public class Project4 { static final int INITIAL_CAPACITY = 5; public static void main( String args[] ) throws Exception { if (args.length = 0 ) return false; // DO NOT INSERT ANY DUPLICATES INTO ARRAY // convert/decode index back to non negative // write a loop that opens up a slot at [index] arr[index] = newVal; // LEAVE THIS HERE. DO NOT REMOVE return true; } // REMOVE ALL COMMENTS FROM BSEARCH JUST BEFORE HANDIN static int bSearch(int[] a, int count, int key) { return 0; // JUST TO MAKE IT COMPILE. } }// END PROJECT4 

P4input.txt

100 89 65 46 32 90 50 38 67 71 42 92 99 57 90 89 98 34 85 19 60 15 99 79 57 

This is my code but it has a bug, it doesnt work, but i believe it is almost working.

/* Project4.java InsertInOrder with bSearch optimization to compute insertion index */ // STUDENT STARTER FILE // YOUR NAME/ID:

import java.util.*; import java.io.*;

public class Project4 { static final int INITIAL_CAPACITY = 30; public static void main( String args[] ) throws Exception { if (args.length

while ( infile.hasNextInt() ) { if ( count==arr.length ) arr = upSizeArr(arr); if (insertInOrder( arr, count, infile.nextInt() ) ) ++count; } arr=trimArr(arr,count); // Now count == .length printArray( arr ); // we trimmed it thus count == length so we don't bother to pass in count } // ############################################################################################################ static void printArray( int[] arr ) { for( int i=0 ; i

if ( index >= 0 ) return false;

// convert/decode index back to non negative else { index = -(index+1); //System.out.println("count =" + count); for (int i=(count-1); i a[mid]) lo = mid+1; else if (key

INSERT IN ORDER OPTIMIZED BY A BSEARCH Background . Starter nie: Project4.java Input file: P4input.txt In lecture we discussed the hinary search algorithm which searches 2 sorted way for a key and returns either the index of where it was forand, or if not found. returns the index of where it helongs. In such a case this becomes index is enca s a negative number to distinguish it from heirs confused with a found index The encoding is as follows: addita index then negate. In lecture we also discussed the insertinOrder algorithm which reads sequence of values from a source text file and inserts them into an almay keeping them SOUTH as och value andded to the anny. You will your search to determine where that mimberllons in the array, rhan Paing Ordaranda will writen laptopen slor for tharlament and patthavnlue into the array Thaallra berrel will figure out where thc uerky belongs in OxlayN), whereas Linears will rake ON) Using a binary scarca instead of a simple linear sean to figure out w c tos no kcy goes is an optimization of the insertinder algorithm when tosincetOrder gets the index back from the bicaly scuch, it must examine that she to soc if it is acgativo. If so, it must be decoded back to a scal index. The decoding is actually the same operatica: add one tbca negate it back to positive Your bearch algorithm look for the number 19 the ley 19 was FOUND AS! the key 12 was NOT FOUND but BELONGS at : To prevent this confusion your bearch will take the index number 3 und and is in a native number w 13011) [131300 UUD It can't find it so instead of returning a traditional to indicate NOT FOUND it must return the index when it belongs in the array. However, it can't just return the index 3 because that would be confusing to whoever called bereh The caller would not be able to tell if thas return valo MRR encodedades index+1), will return the number 4 lose to hit the supone slot Now, when your insertinOrder gets an inde buel. Lrum b urch it will look at the number iftis nesut If its negative it must be decided back to the intended index value of 3. This oneration is the verse of the encoding. It is done by adding th i ng the value AT 151151110101 0111111 decudindex--encoded indexed), 1 pr e 3 which is where y 12 bleya You only do this decoding of the ind you got back from b archa wa negative Now you can still open u kup in the array to mula slot Ite the new key And copy the new key 13 tto skat 3) arr --> 131 15) [11] [12] [13] [66] [11[1 How you will be graded Your program once submitted will he initially script graded for Het minut ASAP and then hack read by the me lo venly that you write a genuine insert in der algoritmas prescribed and write your own version of binary such. You are no. allowed to leave in the call to Amy.sont that we put in your starter file. That call is just to ensure that your insertinander is getting the correct index value to work with so you can debug yorar insertinOrder hefare you work on your hinary search $ java Project 4 Plinut.txt 13 19 32 34 38 42 46 50 57 40 65 67 71 29 89 89 90 92 98 99 100