[Solved] CSE 330 LABORATORY — Week 6

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:

1. You may use your own h or the standard template library <vector>.
2. Your binary search implementation must be iterative, not
3. Binary search must be implemented as a function.
4. 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).