Binary search function function, domain and max number of iterations as parameters

user_18803132 0
Viewed 537

I'm quite new to python and algorithms, I'm struggling with the following function. Can anyone assist?:

For this question, you will be required to use the binary search to find the root of some function () on the domain ∈[,] by continuously bisecting the domain. In our case, the root of the function can be defined as the x-values where the function will return 0, i.e. ()=0 For example, for the function: ()=2()2−2 on the domain [0,2] , the root can be found at ≈1.43 .

Constraints

Stopping criteria: ||()||<0.0001 or you reach a maximum of 1000 iterations. Round your answer to two decimal places. Function specifications

Argument(s):

f (function) → mathematical expression in the form of a lambda function. domain (tuple) → the domain of the function given a set of two integers. MAX (int) → the maximum number of iterations that will be performed by the function.

My current solution is not quite there:

### START FUNCTION
def binary_search(f, domain, MAX = 1000):
    
### END FUNCTION```

---------------------------------

Required input:

f = lambda x:(np.sin(x)**2)*(x**2)-2
domain = (0,2)
x = binary_search(f,domain)
x

----------------------------------

Expected output:
1.43
python
1 Answers

The only thing your code miss is the reassignment of the variable MAX:

MAX = MAX - 1

Then I obtain as expected 1.43.

And as noticed by @Stef, including the conditions in the while loop would be cleaner than using return in the middle. Currently, your loop is equivalent to a while True as start will always be smaller than end (assuming that the passed domain is in the right order).

This should be a bit cleaner:

def binary_search(f, domain, MAX = 1000):
    start, end = domain
    if start >= end:
        raise ValueError("Domain is empty")
    mid = (start + end) / 2
    fmid = f(mid)
    step = 0
    while abs(fmid) > 0.0001 and step < MAX:
        if fmid < 0:
            start = mid
        else:
            end = mid
        mid = (start + end) / 2
        fmid = f(mid)
        step += 1
    return round(mid, 2)
user_181596030
Related