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) < y
comparison finds out whether the
current value of x
is mapped to something below
y
.
The search function has the name ysearch()
because it searches
the largest integer x with f(x) < y
. The place
where ysearch()
has to be modified is the current exhaustive
search procedure which should be replaced by a faster algorithm. This portion
of code is between comments. JavaScript comments are between slashes and
stars: /* this is a comment */
.