More With Arrays Solutions
COMP 1010 Home > More With Arrays > Solutions
IntroductionThis section contains all of the solutions to the review questions and exercises for More With Arrays chapter.
|
---|
{{{Body}}}
Review Questions
Passing Arrays using Methods
Working with Paritally Filled Arrays
Arrays of Strings
Searching Arrays
- No, the array does not need to be sorted for a linear search, but it is more efficient if it is.
- Yes, the array does need to be sorted for a binary search.
- A binary search is more efficient.
- The binary search.
Sorting Arrays
Parallel Arrays
- Parallel arrays are no more tied together than two regular int and string variables are. the only thing tying them together is their common size and your use of them.
- No, you must make a customized sorting method that keeps all data in the arrays in parallel.
Exercises
Apply the binary search
Question:
Modify the binarySearch() algorithm to keep count of how many elements the algorithm checks to find the desired element. Print out each checked element's value (in other words, the value compared with the search value.)
Solution:
First, to keep count of the number of elements checked, we must at a variable, count. This variable will be incremented (count++) each time we do a comparsion (three times.)
Secondly, to print each element checked, we can simply add a System.out.println() statement at the end of our while loop. For esthetics only, we also print out the count variable.
public static int binarySearch(int[] list, int searchValue) { int left; //left element index int right; //right element index int middle; //middle element index int result; //element that searchValue was found in int middleElement; //middle value (comparing) int count; //# element checked during search result = -1; //return -1 if searchValue is not found left = 0; //left index starts at the first element right = list.length-1; //right index starts at the last element count = 0; //we haven't checked any elements yet while ((left <= right) && (result == -1)) {//left and right boundaries do not overlap and searchValue is not found middle = (left + right) / 2; middleElement = list(middle); if (middleElement == searchValue) {//we have found our searchValue result = middle; count++; } else if (middleElement < searchValue) {//need to discard left portion of array left = middle + 1; count++; } else if (middleElement > searchValue) {need to discard right portion of array right = middle – 1; count++; } System.out.println("Value compared: " + middleElement); System.out.println("Number of elements counted: " + count); }//while return result; }//binarySearch()
Arrays of Strings
public class PrintCities // We want an actual program here... This needs to run as-is! { // Bonus points: Use of constants final String WPG = "Winnipeg"; final String TOR = "Toronto"; final String OTT = "Ottawa"; final String EDM = "Edmonton"; final String VAN = "Vancouver"; // Bonus points: Use of a method public static void doThePrint() { String[] cities = new String[5]; // We did assume that cities could be hard-coded! // Any cities could be used, really... YMMV cities[0] = WPG; cities[1] = TOR; cities[2] = OTT; cities[3] = EDM; cities[4] = VAN; // Bonus points: Use of a loop for( int i = 0; i < cities.length; i++ ) { System.out.println( cities[i] ); }// end for }// end doThePrint() public static void main( String[] args ) { doThePrint(); // Bonus points (as above) }// end main }// end PrintCities