Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 815

10. What indexes will be examined as the middle element by a binary search for the target value 8 when the search is
run on the following input array? Notice that the input array isn't in sorted order. What can you say about the binary
search algorithm's result?
int[] numbers = {6, 5, 8, 19, 7, 35, 22, 11, 9};
11. What modifications would you have to make to the selectionSort method to cause it to sort an array of double
values rather than one of integer values?
12. How many calls on the mergeSort method are generated by a call to sort a list of length 32?
13. Consider the following array of int elements:
int[] numbers = {7, 2, 8, 4, 1, 11, 9, 5, 3, 10};
a. Show the state of the elements after five passes of the outermost loop of selection sort have occurred.
b. Show a trace that is two levels deep of the merge sort algorithm. Show the splitting of the overall array, plus one
level of the recursive calls.
14. Consider the following array of int elements:
int[] numbers = {7, 1, 6, 12, -3, 8, 4, 21, 2, 30, -1, 9};
a. Show the state of the elements after five passes of the outermost loop of selection sort have occurred.
b. Show a trace that is two levels deep of the merge sort algorithm. Show the splitting of the overall array, plus one
level of the recursive calls.
Exercises
1. Suppose the following array has been declared:
// index 0 1 2 3 4 5 6 7 8 9
int[] list = {-2, 8, 13, 22, 25, 25, 38, 42, 51, 103};
What indexes will be examined as the middle element by a binary search for each of the following target values?
What value will be returned?
a. 103
b. 30
c. 8
d. -1
2. To which complexity class does each of the following algorithms belong? Consider N to be the length or size of the
array or collection passed to the method.
a. public static int[] mystery1(int[] list) {
int[] result = new int[2 * list.length];
for (int i = 0; i < list.length; i++) {
result[2 * i] = list[i] / 2 + list[i] % 2;
result[2 * i + 1] = list[i] / 2;
}