Binary Search

1. Suppose that that we have an array called list initialized as follows:

int[] list = {-2, 8, 13, 22, 25, 25, 38, 42, 51, 103};

This would construct the following array:

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+

| -2 | 8 | 13 | 22 | 25 | 25 | 38 | 42 | 51 | 103 |

+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+

Note that the method calls below is of the form: binarySearch(int[] a, int low, int high, int target)

a) What values would low, high and mid take on for the following call:

binarySearch(list, 103, 0, 9, 103)

and what value would be returned?

b) What values would low, high and mid take on for the following call:

binarySearch(list, 2, 8, 30)

and what value would be returned?

Efficiency and Big-Oh Notation

2. Approximate the value of sum after the following code fragment, in terms of variable n in Big-Oh notation.

int sum = 0;

for (int i = 1; i <= n - 3; i++) {

for (int j = 1; j <= n + 4; j += 5) {

sum += 2;

}

sum++;

}

for (int i = 1; i <= 100; i++) {

sum++;

}

3. Approximate the value of sum after the following code fragment, in terms of variable n in Big-Oh notation.

int sum = 0;

for (int i = 1; i <= n; i++) {

sum++;

}

for (int j = 1; j <= n / 2; j++) {

sum++;

}

Sorting

4. Consider the following array of int values.

[7, 1, 6, 12, -3, 8, 4, 21, 2, 30, -1, 9]

Write the contents of the array after 4 passes of the outermost loop of selection sort.

Write the contents of the array during each of the the recursive calls of merge sort.