Assignment 14 - Binary Search in Mathematics

You can download this homework and set the permissions with the commands 
      cd ~/public_html
      wget http://www.comp.nus.edu.sg/~gem1501/assignment14.html
      chmod 755 *.html
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).

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 halfves 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 command "u = f(17);" and similar you can access f at any input.
  5. The value of y is in a global variable with the same name. So the comparison "f(x)<y" 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. There is a comment below this line. Java Script comments are between slashes and stars: /* this is a comment */

Java Script starts here.

Java Script ends here.