General discussions: Binary Search Again

Christopher Matthews 2014-11-14 08:23:13

Hey everybody,

I'm having a very hard time understanding the binary search problem... I know it should be very easy, but for some reason it just doesn't make much sense when reading the wiki for it... Would anybody mind explaining the algorithm in the simplest way possible?

Thank you,
Christopher P. Matthews

Rodion (admin) 2014-11-14 10:31:57

Hi! Thanks for your message!

If you mean this task then probably you are right - it is bit more complicated than it should be. (It was created when the site was young and had less agility in checking responses etc - that is why it is somewhat ugly.)

So if it is not urgent right now, I dare to advice skip it for now and return to it later. Either you meanwhile will learn bit more about math functions and will be able to solve this one easier - or it may happen that I will try to add some picture (or video?) to this task - or even another simpler task of the same kind.

Rodion (admin) 2014-11-28 14:01:52

Aha, I see that you overcome this problem at last and it surrendered to your efforts!

Congratulations and, well, I hope all problems you encounter in your professional life will surrender to you in the same manner :)

Sergey Lyakh 2014-12-14 19:25:27

Hi! I can't get result better than 0.00001. Any hint, please?

Rodion (admin) 2014-12-15 04:03:45

Hi, thanks for your question!

I had a peek into your solution - it seems you are rounding intermediate results:

double p = formatDouble(b/a,7);
double q = formatDouble(c/a,7);
double r = formatDouble(d/a,7);

so losing precision before calculation. I'm not sure why you are doing this on such an early stage - probably it is better to avoid any rounding before you are going to output final result...

Hope this may help. Feel free to write more if not! :)

Sergey Lyakh 2014-12-23 13:10:31

I removed format function, but it doesn't help... I get "CPU time limit exceeded (core dumped)"..

Rodion (admin) 2014-12-23 16:57:49

Hi! I've studied your code a bit.

I'm afraid it does not look like "binary search". You have only one variable x changing and you either multiply it by 1.5 or divide by 2:

double x = 50;
while (!isClose)
{
    // some calculations
    if((temp)>0){
        x= x -x/2;
    } else {
        x= x +x/2;
    }
}
System.out.print(x + " ");

But this simply will not work. Imagine that target value is 60. You add a half to your x=50 and get 75, then you subtract one half to get 37.5. Then you multiply it and get 56.25, then divide and get 28, then multiply again and again to get about 63, then divide to get 32 and so on and so on.

You are wandering with a single variable around the point. Probably you may eventually to get close to it, but this will not necessarily be soon!

Instead you should have two variables xmin=0 and xmax=100 and on each iteration choose x in the middle between them. Then you look into which half the solution hits and update one of these variables - i.e. either xmin = x or xmax = x... You may find bit more detailed info in the related articles...

Sergey Lyakh 2014-12-23 19:39:13

Thank you! Two variables have helped:)