Requirements (binary_search_function.h)

Implement the binary_search_function function and upload your implementation as files named "binary_search_function.h" and "binary_search_function.cpp".

Did you know you can use Binary Search for more than just vectors? You can use it for more than just collections of things too. You can even use it for functions!

When we used Binary Search in class, we had a sorted list of words and wanted to find a word. What does Binary Search need?

• A way to represent a lower and upper bound
• A way to calculate a middle point between the lower and upper bound
• Sorted input -- or at least input such that input[i] =>

Say for example, that you don't have a sqrt function, so you want to make a function that approximates it for non-negative numbers (like 0 or 3.141592 or 1234567890). One way you can do that is to just... guess and check.

For example, you know that the square root for 5 is between 2 and 3. You know the value you're searching for is somewhere in the range from 2 to 3. You could guess that it's in the middle (2.5) and then check (2.5 * 2.5 == 6.25). 5

The sqrt function has all of the requirements for Binary Search if you're searching for some x that's bigger than 0!

• You can represent a range of possible numbers (0 sqrt(x) x)
• You can calculate some point in the middle of that ranges
• The input is sorted (in math terms, we say that the function is monotonically non-decreasing) because sqrt(x) sqrt(x + some_positive_number_like_1)

Your goal in this program is to write a binary_search_function that'seven more general. binary_search_function takes in an std::function like double square(double x) { return x * x; }, if you wanted to calculate the square root of a number.(double)>

If you're not sure where to start, try implementing a binary search function that calculates the square root of a number instead of one that takes in const std::function& f.(double)>

binary_search_function.h

#include // DBL_MAX

#include // std::function

double binary_search_function(

const std::function& f, // function to binary search(double)>

double value, // value we are searching for

// max_err is how close we want our answer to be. For example,

// if we passed max_err=0.0, then binary_search_function returns exactly

// the right answer*

double max_err=0.001, // maximum allowed error of value being passed to f

double lower_bound=-DBL_MAX,

double upper_bound=DBL_MAX);

binary_search_function.cpp

#include "binary_search_function.h"

double binary_search_function(

const std::function& f, // function to binary search(double)>

double value, // value we are searching for

double max_err, // maximum allowed error of value being passed to f

double lower_bound,

double upper_bound) {

// your code here...

}

Simple Manual Test program

#include

#include

#include "binary_search_function.h"

using namespace std;

double square(double x) {

return x * x;

}

int main() {

for (double x = 0; x

// Approximate the square root of x by binary searching the square function.

// For any positive number, we know the square root of x is between 0 and x.

double approx_sqrt_x = binary_search_function(square, x, 0.0001, 0.0, x);

cout

}

return 0;

}

$ clang -pedantic -Wall -lm -lstdc++ -std=c++20 -o example hw01/test_binary_search_function.cpp hw01/binary_search_function.cpp

$ ./example

sqrt(0) 0

sqrt(1) 0.999969

sqrt(2) 1.41422

sqrt(3) 1.73204

sqrt(4) 2.00003

sqrt(5) 2.23606

sqrt(6) 2.44945

sqrt(7) 2.64575

sqrt(8) 2.8284

sqrt(9) 2.99999