java - sorting

2007-03-04 2:33 am

Given the following Java code:

/* Recursively search a[0: size – 1] for x.
size indicates a.length */
private static int goodSearch(int size) {
if (size < 0)
return -1;
if (x.equals(a[size – 1])
return (size – 1);
return goodSearch(size – 1);
}

How many comparisons between the array a and the variable x are made by the recursive method goodSearch()?

and explain that, please ~

回答 (1)

karen chan

2007-03-09 4:16 pm

✔ 最佳答案

Case 1: size < 0, a = []
Number of comparisons is 0 because the function returns -1 immediately.

Case 2: a = [1, 2, 3, 4], size = 4, x = 5
The function starts by comparing a[3] (which is 4) with x, failed and try with size = 3 etc...
It is not possible to find a match, the number of comparisons is the value of size.

Case 3: a = [1, 2, 3, 4], size = 4, x = 3
The function starts by comparing a[3] (which is 4) with x, failed and try with a[2] (which is 3) which is the same as x.
When a match can be found, it depends on where the match is. Let's say i is the index of the match, (in the example, i = 2), the number of comparisons is (size - i).

I hope the explanation is clear. :)

👍 0 👎 0