Assignment 14 - Binary Search in Mathematics

1. Getting Started.

   Please refer to this page for information on how to work on your assignment.

2. Outline

   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).

3. What has to be done in detail

   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:

   1. The value x is at least 0 and less than y: f(0) = 0 and f(z) > z for all z > 0 ;
   2. The function f is a strictly increasing function;
   3. One method to implement the search is to start with a large enough interval and to split it in halves in each step. Then one checks whether it evaluates a the point between the halves to a value below y or not and takes the according half. One has to make sure that the splitting point is always an integer.
   4. The function value can be accessed by simply calling 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.
   5. The value of y is in a global variable with the same name. So the 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 */.