search

bqi343 / cp-notebook

General Resources for Competitive Programming
Creative Commons Zero v1.0 Universal
2.39k stars 416 forks source link

Fix Bug at Binary Search #20

Closed mohanadtalat91 closed 2 years ago

mohanadtalat91 commented 2 years ago

Overflow will be happen at this line because if "hi= 2147483647" & "lo= 1" then the sum of "lo"+"hi" will be overflow. So try to use the following formula to prevent overflow - - > " mid = lo + ((hi-lo)/2) "

I'll add PR.

https://github.com/bqi343/USACO/blob/26d1428ccd789e2b87c8e34f217f3d711d45fc35/Other%20Implementations/04%20-%20Sorting%20and%20Searching/Binary%20Search%20(4.3).cpp#L10

bqi343 commented 2 years ago

hi-lo could overflow as well. In C++20, you can use https://codeforces.com/blog/entry/96040?#comment-851220. Anyways, the point of that snippet is just to solve https://open.kattis.com/problems/guess, so it doesn't really matter.

mohanadtalat91 commented 2 years ago

I think it will not be any overflow in case hi-lo, and this is efficient way to get middle, because (hi+lo)/2 will work only in best case. But (lo+((hi-lo)/2) will work in different scenarios best & worst.

https://www.geeksforgeeks.org/binary-search/