[Introduction to Algorithms, CLRS] Exercises 2.1-3

This is a solution for Introduction to Algorithms. I write this for my study purpose.

Exercises 2.1-3

Consider the searching problem:

Input: A sequence of n numbers A = <a1,a2, ... ,an> and a value v.

Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.

Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

Answer:

LINEAR-SEARCH(A, v) 

1     for i = 1 to A.length 

2         if A[i] == v

3             return i

4      return NIL

At the start of the each iteration of the for loop of lines 1-3, the subarray A[1..i−1] consists of the elements that are not equal to v.

Initialization: We start by showing that the loop invariant holds before the first loop iteration, when i =0. The subarray A[1..i-1], therefore, consists of no element, which is equal to v.

Maintenance: The body of the for loop checks if A[i] is v until i reaches A.length. After each loop, if A[i] equals to v, the index will be returned. After the last loop, if v is not found in A, then NIL will be returned.

Termination: The loop terminates in either of the following cases:

1) We have found index i such that v = A[i].

2) We reached the end of the array, i.e. we could not find v in the array A. So, we return NIL.

In either case, our algorithm does exactly what was required.

Source: https://atekihcan.github.io/CLRS/E02.01-03/