[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.