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
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()