Loop invariant for linear search

Correctness: Loop invariant At the start of each iteration of the for loop we have A[j] 6= v for all j < i.

Initialization Before the first loop iteration the invariant holds since the statement is empty.

Maintenance The loop invariant is maintained at each iteration, since otherwise at the i-th iteration there is some some j < i such that A[j] = v. However, in that case for the j-th iteration of the loop the value j is returned, and there is no i-th iteration of the loop, a contradiction.

Termination When the loop terminates, there may be two cases: one is that it terminates after i ≤ length(A) iterations, and returns i, in which case the if conditional ensures that A[i] = v. The other case is that i exceeds length(A), in this case by the loop invariant we have that for all j ≤ length(A) A[j] 6= v, this returning NIL is correct.

q2

2.2-3 Consider linear search again (see Exercise 2.1-3). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in ‚-notation? Justify your answers.

Solution:

Since the probability of v = A[i] is 1/n for all i = 1, . . . , n, and we need to check exactly i elements when v = A[i], we have that expected value of the number of checks is

1 / n (1 + 2 + · · · + n) = 1 /n n(n + 1)/ 2 = n + 1 /2 .

In the worst case it is n. The avarage case running time is c · n+1 /2 = Θ(n) since for all n ≥ 1 we have

1 /2 n ≤ n + 1/ 2 ≤ n.

The worst case running time is also Θ(n).

q3

2.3-5 Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search.