Problem 34 Binary Search

Check how you are doing x^3

I'm having the same problem. My check with answer plugged in gives me 4.898771521766321e-08.
check = a * x + b * math.sqrt(x**3) - c * math.exp(-x / 50) - d

NB: Solution should be calculated with precision 0.0000001 = 1e-7 or better.

Yes, Vadim is correct - the answer need not be "indefinitely exact" :)

Right but I thought the answer was supposed to be 0?

Answer is not the value of this expression, but the value of x which, if plugged into expression, yields value close to 0.

Or have I misunderstood your question?

You got it. When I plug x in with the answer given for the example problem it's returns a value not equal to 0

I feel dumb I didn't realize that was less than 0 but closest.

Okay so I solved the problem but the way i broke out of my loop I don't like. I definentally feel like I cheated. if step > 32: return print('%.7f ' % (x)) that's what i used to break out since I couldn't figure out how to get it to stop close to the answer. Interesting enough it was correct for all the answers.

Mario,

I've taken a look at your code, and I'd like to propose some hints.

On lines 40-45, while processing each of the input's test cases, you have the following code:

for l in testdata:
    for a in l[::4]:
        for b in l[1::4]:
            for c in l[2::4]:
                for d in l[3::4]:
                    bsearch(float(a),float(b),float(c),float(d))

There's a couple of minor problems with this. First, you could make this code more compact and pythonic by taking advantage of the power of the tuple. Second, you've got unnecessary list splicing and control looping that might make your code tougher to debug for later problems with lists of variable length from test case to test case. Instead, try this code:

for l in testdata:
    a,b,c,d = l
    print('%.7f ' % (str( bsearch(float(a),float(b),float(c),float(d)) )) )

If you're not familiar with tuples and assigning variables from tuples, I challenge you to try print(a,b,c,d) before the function call to see what happened inside this loop. Also note that I moved the print statement outside the function. It's better to have a function return a value rather instead of returning None after performing a side effect (like printing). It will make the function more reusable.

Next, you mentioned that you don't like the way you broke out of the control loop within the bsearch function. I see two issues. First, you have a range generator assigned to i within a loop, but you never use the value of i. Currently, you run until you've done 32 iterations. This works for our smaller monotonic coefficients. But if the difference between minimum and maximum values in the codomain of f(x) = a * x + b * math.sqrt(x**3) - c * math.exp(-x / 50) - d for a given domain of x is large, you might not get a zero to the function with the necessary precision.

Instead, consider the following code inside your bsearch() function.

    while abs(check) > differ: #### Note that the looping condition has changed
        ####for i in range(x, y):#### Line no longer needed.

        ###TO DO: Calculate the median of the boundaries, and recalcuate <check>
        ...

        ####step += 1#### Line no longer needed.

        ###TO DO: Determine if check was too high, too low, and move your search boundaries
        ###       to cover half of the previous range.
        ###       (one boundary stays the same, the other becomes the old median value)
        ...

        ####if step > 32:#### Line no longer needed.

    ###TO DO: now that you've found a median value that provides a zero within the needed <differ> precision,
    ###       return that median value from the function.            

Once you've improved your code, you can take a look at my implementation of the Binary Search to compare.

Awesome cole yea thats alot to go thru. I figured later I could've exited the loop that exact same way. Thanks for the help tho.

I have a different problem than any that I see listed above. I am getting an error message because my exp function is being performed on a nonpositive number. Looking at the equation, it seems inevitable that this will happen for any positive value of x, because it is set to negative in the parentheses (-x/50). What am I not understanding correctly here? Thanks for any help.

> I am getting an error message because my exp function is being performed on a nonpositive number

Well, it is strange for exponent is well defined for negative values.

Technically exp(-x) = 1 / exp(x). See for example: http://ideone.com/ErAgBk

I'm sorry for this problem being bit more mathy than it should. We have array-based version of binary search in the problems list - but it was added later...

No problem, thanks for the explanation. I think I am reaching the limit of my math knowledge on a challenge like this one. But I will change my code to the equivalent you have listed above, and try it again.

Good afternoon and sorry, I'm new in this place, I don't understand if the function exp() refers to number "e" raise the power ... or if its meaning is another. Thanks.

Hi and welcome. exp(x) is e to the power x.

Thank You for your help Quandray!

This problem is kicking my butt! Can't wait to solve it. . .

What should be the initial value of x and the way given in this article https://www.codeabbey.com/index/wiki/binary-search is the one used to change the value of until it meets the condition that 0<= x<=100?

Hello! I'm not sure I understand the question well, but your initial values are x_right and x_left - the ends of the range at which you are searching for root. In this problem we want to search for root between x=0 and x=100. According to problem statement it is guaranted that function is monotonic (i.e. it would be negative at x=0 and positive at x=100) - and we want to find such x where it crosses the line of y=0. Hope this helps... Though probably I should add a picture...