Complete 2.1-3

3 files changed, 82 insertions, 0 deletions

diff --git a/0x01/README.md b/0x01/README.md
index 201cb88..ee4fe11 100644
--- a/0x01/README.md
+++ b/0x01/README.md
@@ -107,6 +107,22 @@ Submit your solutions to the following exercises and problems:
     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.
+
+
 1. Exercise 2.2-3 from the textbook (10 marks)
 
     Consider linear search again (see Exercise 2.1-3). How many elements of the
diff --git a/exercises/2.1-3/search_test.go b/exercises/2.1-3/search_test.go
new file mode 100644
index 0000000..c4ed033
--- /dev/null
+++ b/exercises/2.1-3/search_test.go
@@ -0,0 +1,39 @@
+package main
+
+import "testing"
+
+func linearSearch(A []string, v string) int {
+	i := 0
+	length := len(A)
+
+	for i < length && v != A[i] {
+		i = i + 1
+	}
+	if i == length {
+		return -1
+	}
+
+	return i
+}
+
+func TestSearch(t *testing.T) {
+	t.Run("Found", func(t *testing.T) {
+		items := []string{"apples", "bananas", "shrimp", "tuna"}
+
+		result := linearSearch(items, "shrimp")
+
+		if result != 2 {
+			t.Fatalf("Expected 2, Got: %v", result)
+		}
+	})
+
+	t.Run("Not Found", func(t *testing.T) {
+		items := []string{"apples", "bananas", "shrimp", "tuna"}
+
+		result := linearSearch(items, "chips")
+
+		if result != -1 {
+			t.Fatalf("Expected -1, Got: %v", result)
+		}
+	})
+}
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: