0

I used to do lo+(hi-lo)/2 in binary search in java

As we do not have int overflow in python, Do I need to do it in python?

(lo+hi)//2 is enough?

I am not using any library

references Why we write lo+(hi-lo)/2 in binary search? Integer overflow in Python3

Atul Takekar
  • 51
  • 13
  • The answer is you don't **need** to do it one way or the other. – Stephen C Sep 18 '22 at 02:32
  • 2
    The best way to do it in Python is `(lo+hi)//2`. Or `(lo+hi)>>1`. – Tom Karzes Sep 18 '22 at 02:34
  • I don't think integer overflow will be relevant, since there is a limit on the max size of a Python list; see https://stackoverflow.com/questions/855191. It will be less or equal to the platform's max positive integer value. – Stephen C Sep 18 '22 at 02:36
  • @TomKarzes - but the point is that the way that the OP *has been* doing it works fine, even if it is not the most efficient and/or most pythonic. – Stephen C Sep 18 '22 at 02:37
  • @StephenC Yes, and I implied it was both the most efficient and the most Pythonic. That's what I meant by "best". Also, your comment seems to ignore the fact that Python has bignums. All the memory in all the computers in the world wouldn't even come close to causing bignum overflow in Python when computing list indices this way. – Tom Karzes Sep 18 '22 at 03:35
  • Well yes. But python lists are in practice limited to either 2^31 -1 or 2^63 -1 elements. Bignums should not come into the equation. – Stephen C Sep 18 '22 at 03:41
  • @StephenC I've done binary search on `range`s, which can be far larger than `list`s... (still not a problem, though). – Kelly Bundy Sep 18 '22 at 14:28
  • Yea ... 2^63 - 1 is a really big number, and yet it it is not a bignum :-) – Stephen C Sep 18 '22 at 23:24
  • @StephenC If that's a response to me: Why 2^63 - 1? – Kelly Bundy Sep 18 '22 at 23:35

0 Answers0