Find.c - Binary Search probable integer overflow

Question

Here's the gist: https://gist.github.com/Securiteru/a83e4f1a028acd0b1013def793b5dcdc

And the output: ... 60697 61151 61190 61275 61460 61608 61618 61746 61750 61822 62111 62178 62183 62311 62448 62454 62522 62558 62681 62699 62724 62853 62856 62885 62953 62972 63007 63052 63104 63189 63191 63244 63341 63455 63488 63521 63553 63735 63737 63745 63752 63776 63815 63877 63977 64113 64187 64344 64387 64394 64491 64553 64592 64657 64663 64864 64867 64904 64925 65050 65196 65319 65474 mid is: 499 249 124 61 30 14 6 2 0 1 Didn't find needle in haystack.

Basically what I did, if you didn't see in the gist, I asked the program to show me all the elements of the randomly generated array (to ensure it's sorted properly, I think it is) and then the MID after each iteration, I have a question why does 0 precede 1 and why is that? Is it an integer overflow of sorts, is it a code bug, I would appreciate any feedback regarding this issue.

Answer 1

Your values are like

+---+---+---+---+
|min|max|mid|<>=|
+---+---+---+---+
|  0|999|499| < |
|  0|498|249| < |
|  0|248|124| < |
|  0|123| 61| < |
|  0| 60| 30| < |
|  0| 29| 14| < |
|  0| 13|  6| < |
|  0|  5|  2| < |
|  0|  1|  0| > |
|  1|  1|  1|< >|
+---+---+---+---+

the value you searched for is between the smallest and third-to-smallest in your array, but does not equal the second-to-smallest (the indices don't allow for knowing whether it's more or less). It searches 0 first as integer division truncates, so (0+1)/2 is 0.

Your bubble sort is done without any optimisations, and many of the comparisons aren't necessary.

Who says "probable integer overflow"? The only place I see which might overflow easily is mid=(min+max)/2;, in case of min and max being relatively large positive numbers (or basically, max being really large and value being very high so min approaches max), their sum might be negative. Let's hope we won't see arrays that large. If int is an 8-byte integer, this is pretty unlikely (unless somebody passed an invalid n, in which case we'd have a segmentation fault long before the integer overflows)