Complete 2.1-3

1 files changed, 27 insertions, 0 deletions

diff --git a/notes.md b/notes.md
index d56c196..b2e9cfc 100644
--- a/notes.md
+++ b/notes.md
@@ -318,3 +318,30 @@ for j = 2 to A.length
     i = i - 1
   A[i+1] = key
 ```
+
+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.
+
+```plaintext
+i = 0
+for i < A.length and v != A[i]
+  i = i + 1
+  if i >= A.length
+    return NIL
+
+return i
+```
+
+* initialization: initialize `i` to first index of first element
+* maintenance: continue looping if `i` is less than size of `A` and `A[i]` is
+  not equal to the target value `v`.
+* termination: terminate loop when the key matches the target value.
+
+2.1-4: