Please refer to this page for information on how to work on your assignment.
Binary search is a method to find in an ordered list a datum. In Mathematics, one can use the same principle in order to find a place where a monotonically increasing function takes a certain value. The function will be chosen with some random parameters, but it will be guaranteed that f(0) = 0 and f(x) > x for x > 0. Given a value y > 0, the task is to find the largest integer x with f(x) < y. The algorithm should have order O(log(n)). Here the parameter n is the number of integers between 0 and y because any of them is a possible solution, so n = floor(y).
Within the framework of this exercise, the whole binary search algorithm should be implemented. The current implementation is exhaustive search which is inefficient for large y. The following facts can be used:
f(). If you want to assign
f(17)to a variable
u, you can do it by the
u = f(17);command and similarly you can access f at any input.
f(x) < ycomparison finds out whether the current value of
xis mapped to something below
The search function has the name
ysearch() because it searches
the largest integer x with
f(x) < y. The place
ysearch() has to be modified is the current exhaustive
search procedure which should be replaced by a faster algorithm. This portion
/* this is a comment */.