diff options
Diffstat (limited to '0x01/README.md')
| -rw-r--r-- | 0x01/README.md | 19 |
1 files changed, 19 insertions, 0 deletions
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) |