0

Trying binary search but decimal, floating points making it inaccurate. Why? 

print('Enter your input:')
n = input()


def binarysearch(n):
        j = float(n)/2
        i = k = j/2
        while round(i,2)*round(i,2) != float(n):
                if round(i,2)*round(i,2) < float(n):
                        k = round(i, 2)
                        i += round(((j-i)/2),2)
                        round(i, 2)
                        print(i, 'less') # just for tracking
                if round(i,2)*round(i,2) > float(n):
                        j = round(i, 2)
                        i -= round(i/2,2)
                        round(i, 2)
                        print (i, 'more') # just for tracking

       return i


print (binarysearch(n))

Output - 

Enter your input:
9
3.00999999999998
3.37 less
1.6800000000000002 more
2.52 less
2.95 less
3.16 less
1.58 more
2.37 less
2.77 less
2.97 less
3.06 less
1.53 more
2.3 less
2.6799999999999997 less
2.8699999999999997 less
2.9699999999999998 less
3.0199999999999996 less
1.5099999999999996 more
2.2699999999999996 less
2.6499999999999995 less
2.8399999999999994 less
2.9299999999999993 less
2.979999999999999 less
2.999999999999999 less
2.999999999999999

Enter your input:
36
6.009999999999916
4.5 more
6.75 less
3.37 more
5.0600000000000005 less
5.9 less
6.32 less
3.16 more
4.74 less
5.53 less
5.930000000000001 less
6.120000000000001 less
3.060000000000001 more
4.590000000000001 less
5.3500000000000005 less
5.73 less
5.920000000000001 less
6.0200000000000005 less
3.0100000000000007 more
4.510000000000001 less
5.260000000000001 less
5.640000000000001 less
5.830000000000001 less
5.920000000000001 less
5.970000000000001 less
5.99 less
6.0 less
6.0

and numbers that are not square root, the search will never finish.

Majoris
  • 2,963
  • 6
  • 47
  • 81
  • Possible duplicate of [Is floating point math broken?](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) – Hong Ooi Nov 17 '19 at 02:56
  • 2
    You aren't testing for i being the root, you are resting round(i). Then you print i (without round) as your answer. Also, `!=` often goes wrong for floats, you need to test for the difference being less than some number. since you are using round(i,2) you aren't going to get a very accurate answer so maybe a difference <= .1 – Dave S Nov 17 '19 at 03:14
  • I assume you are doing this for practice, but in the off chance that you aren't, you can use `import bisect` and `bisect.bisect(...)`, its pythons built in binary search. It needs an object that implements `__len__` and `__getitem__` though, but its pretty easy to duck type a class to do what you want. – Error - Syntactical Remorse Nov 17 '19 at 03:19

0 Answers0