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

---
 notes.md | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

(limited to 'notes.md')

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