From cff508b47a1cb2eee2da5f748dadeb406861ff28 Mon Sep 17 00:00:00 2001
From: mo khan <mo@mokhan.ca>
Date: Sun, 3 Oct 2021 16:31:56 -0600
Subject: pseudocode for binary search

---
 0x01/README.md | 19 +++++++++++++++++++
 README.md      |  2 +-
 notes.md       | 19 +++++++++++++++++++
 3 files changed, 39 insertions(+), 1 deletion(-)

diff --git a/0x01/README.md b/0x01/README.md
index 60d2bc8..da94bc4 100644
--- a/0x01/README.md
+++ b/0x01/README.md
@@ -158,6 +158,25 @@ Submit your solutions to the following exercises and problems:
     iterative or recursive, for binary search. Argue that the worst case running
     time of binary search is O(lg(n)).
 
+      `BINARY-SEARCH(A, t, s, e)` where `A` is an array and `s`, and `r` are indices into the array such that `s < e` and `t` is the target value to find.
+
+      ```plaintext
+      BINARY-SEARCH(A, t, s, e)
+        length = e - s
+        if length == 1
+          item = A[s]
+        else
+          mid = (length / 2) + s
+          item = A[mid]
+
+        if item == t
+          return mid
+        if item < t
+          return BINARY-SEARCH(A, t, s, mid-1)
+        else
+          return BINARY-SEARCH(A, t, mid+1, e)
+      ```
+
 1. Exercise 3.1-1 from the textbook (5 marks)
 1. Problem 3-1 from the textbook (10 marks)
 1. Exercise 4.1-2 from the textbook (10 marks)
diff --git a/README.md b/README.md
index 135eaaa..f59fa3f 100644
--- a/README.md
+++ b/README.md
@@ -100,7 +100,7 @@ When you have completed this objective, you should be able to
 #### Required Activities
 
 * [X] Study Section 2.3 of the textbook.
-* [ ] Do Exercise 2.3-5 from the textbook as part of Assignment 1.
+* [X] Do Exercise 2.3-5 from the textbook as part of Assignment 1.
 
 ### Section 1.3: Asymptotics
 
diff --git a/notes.md b/notes.md
index eb58099..38a2d88 100644
--- a/notes.md
+++ b/notes.md
@@ -807,3 +807,22 @@ time of this recursive version of insertion sort.
     remaining portion of the sequence each time. Write pseudocode, either
     iterative or recursive, for binary search. Argue that the worst case running
     time of binary search is O(lg(n)).
+
+`BINARY-SEARCH(A, t, s, e)` where `A` is an array and `s`, and `r` are indices into the array such that `s < e` and `t` is the target value to find.
+
+```plaintext
+BINARY-SEARCH(A, t, s, e)
+  length = e - s
+  if length == 1
+    item = A[s]
+  else
+    mid = (length / 2) + s
+    item = A[mid]
+
+  if item == t
+    return mid
+  if item < t
+    return BINARY-SEARCH(A, t, s, mid-1)
+  else
+    return BINARY-SEARCH(A, t, mid+1, e)
+```
-- 
cgit v1.2.3