Xclusive_OR's blog

Help needed in Binary search EDU
By Xclusive_OR, history, 2 months ago, In English

Problem Link

in the good function bool good(double x){ double temp=( x*x + sqrt(x) ); if(temp-c>0) return 0; else if(temp-c<=0) return 1; } why are we doing,

if(temp-c>0) return 0; else if(temp-c<=0) return 1;

instead of return temp-c== 0;

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (5)
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Because binary search is monotonic.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    can u please elaborate a little more, I am having a hard time understanding why <= 0

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If you want to check for every possible value of x then you can write return temp-c==0 in good funtion. but that method gives you tle.so for reducing time limit you need to apply here binary search and making good funtion according to bs.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

u cant do abs(temp-c) == 0 as we r dealing with real numbers here(there is always some error in the precision of float/doubles, so comparison of 2 float/double numbers for the equality is always bit dubious, I mean this what I've learnt and experienced till now) also as pointed by rohit, temp-c == 0 gonna give u TLE.

So, u can do something like abs(temp-c) <= 1e-6

    double l = 0, r = 1e5;
    while (l < r)
    {
        double m = l + (r - l) / 2, temp = m * m - sqrt(m);
        if (abs(temp - c) <= 1e-6)
            return m;
        else if (temp < c)
            l = m;
        else
            r = m;
    }
→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    or rather just go with the template of binary search for answers(involving real numbers), iterate over 100 times or so, then the same thing if the final answer is x with precision error <= 1e-6, then all the value of temp <= x, will be <= c and all the values of temp > x, will be > c. Then finally return l. This is what hv been done in the code u shared ig.

    → Reply