pseudocode for binary search

1 files changed, 19 insertions, 0 deletions

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)
+```