Description
This lab consists of a “free-form” exercise: implement and test the Binary Search Algorithm as discussed in the lecture (lecture notes posted along with these instructions).
Exercise 1: Implement the Binary Search Algorithm. You are on your own except for the following few rules and guidelines:
- You may use your own h or the standard template library <vector>.
- Your binary search implementation must be iterative, not
- Binary search must be implemented as a function.
- You will implement your own main() function to test your binary search function.
Exercise 2: Modify your program from Exercise 1 so that it reports the search effort (in terms of number of equality checks of target against a vector value). Test.
Exercise 3: If there is time. Implement and test a recursive binary search function. Realize: searching for a target in the “left half or “right half” is just another case of searching for a target in a linear arrangement of values. And: when you end up searching in a “half” that is so small that it is empty, you know that the target is not contained.
Credit for this lab: (1) Make sure to sign the signup sheet. (2) No other submissions are required, but keep your work for a follow-up exercise in the future (not the midterm).
