I am busy with a binary search problem in Python.
This is the challenge
Challenge The binary search is considered to be a very powerful algorithm used for locating elements in an already ordered list. Its ability to halve the search space with every iteration is what makes it so efficient. With every iteration we are searching a smaller and more manageable subspace.
Over and above being able to locate items in a discrete list, it can also be applied on a continuous domain. 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. Return:
root (float) → return the root (rounded to two decimals) of the given function.
My code is as follows:
### START FUNCTION
def binary_search(f,domain, MAX = 1000):
(start, end) = domain # get the start and end point
while start < end and MAX:
# get the mid
mid = (start + end) / 2.0
# if we reached to root
if abs(f(mid)) < 0.00000001:
# return rounded
return round(mid, 2)
if f(mid) < 0: # if we are left of root
start = mid # set start to mid
else:
# otherwise go to left
end = mid
MAX -= 1 # decrement max by 1
return round(mid, 2) # return rounded
### END FUNCTION
I am failing tests due to rounding, see below:
PASSED binary_search
FAILED binary_search
Inputs: [<function <lambda> at 0x7f13d9a37d08>, (2, 3)]
assert 2.0 == 2.56
your output: 2.0
expected output: 2.56
FAILED binary_search
Inputs: [<function <lambda> at 0x7f13d99be7b8>, (-2, -1)]
assert -2.0 == -1.43
your output: -2.0
expected output: -1.43
PASSED binary_search
FAILED binary_search
Inputs: [<function <lambda> at 0x7f13d99be8c8>, (-2, -1)]
assert -1.0 == -1.68
your output: -1.0
expected output: -1.68
Example of test passing
binary_search(lambda x:(np.sin(x)**2)*(x**2)-2,(0,2))==1.43
I can not figure out how to correct this. Can anyone guide me on how to alter my solution?