21 ms·
Nearly all binary searches and mergesorts are broken (2006)
- david_allison 4y ago16 years later, it's still incorrect on Wikipedia https://en.wikipedia.org/wiki/Binary_search_algorithm#Procedure https://en.wikipedia.org/wiki/Binary_search_algorithm#Proced...
- enriquto 4y agoBut this is pseudocode. For all you know, it could be implemented in a language whose integers are arbitrary precision, in which case it is perfectly correct and appropriate.
- gp 4y ago> language whose integers are arbitrary precision I’m not sure what this could mean. Could you please share some examples?
- UncleMeat 4y agoPython3 doesn't have a maximum integer and therefore cannot experience overflow when adding two integers, for example. You can keep adding one forever.
- jb_s 4y agoHaskell has arbitary-precision integers. Until you run out of memory, but yeah.
- xdavidliu 4y agoyep, so does Mathematica
- torotonnato 4y agoTake Python for example
- dukoid 4y agoIntegers that are represented by a dynamic number of bits -- as in Python or Javascript BigInt
- kzrdude 4y agoPython does fine with (2**1024 + 3**768) // 2 For example.
- tcoff91 4y agoThis means that the instead of fixed width integer types that have a finite maximum due to being 32-bit or 64-bit etc…, the language could use an integer type that can grow to be as many bytes as is needed to store the number. This is called a BigInt in JavaScript for instance.
- MrJohz 4y agoPython, for example, has arbitrary precision integers. That means that it is theoretically possible to represent any whole number in Python, at least assuming your computer has enough memory to support it. Under the hood, the `int` object can have several different implementations depending on how large the number is. So small numbers will be represented one way, and larger numbers might be implemented as 64-bit integers, but very large numbers are implemented as an array of other integers that can grow arbitrarily large. You can think of the array as being like base-10 representation (so 17,537 might be represented as [1, 7, 5, 3, 7]), although in practice much larger bases are used to make the calculations quicker. Obviously maths with the smaller representations will be quicker than with this array representation, so the interpreter does some work to try and use smaller representations where possible. But if you tried to, say, add two 64-bit signed ints together, and the result would overflow, then the interpreter will transparently convert the integers into the array representation for you, so that the overflow doesn't happen. So the first poster said that the default merge sort implementation on Wikipedia was buggy, because it doesn't protect against overflows (assuming that the implementation used fixed-sized integers). The second poster pointed out that if the implementation used these arbitrary precision integers, then there is no chance of overflow, and the code will always work as expected. You can look up "bigint" which seems to be the term of art for implementations of arbitrary precision integers in most languages. You can also read a bit about how they're implement in Python here: https://tenthousandmeters.com/blog/python-behind-the-scenes-8-how-python-integers-work/ https://tenthousandmeters.com/blog/python-behind-the-scenes-...
- fiedzia 4y ago> Python, for example, has arbitrary precision integers. In the spirit on nitpicking on edge cases: It does, but quiet often you pass a number to some C library (other than stdlib) and C does not honour this arrangement.
- dannymi 4y agoThen an exception is generated. Errors do not pass silently in Python.
- dannymi 4y agoLisp has arbitrary-precision integers by default.
- kupopuffs 4y agonot all languages tie their "integers" to a fixed-bit-length value
- froh 4y agosee "implementation issues" in the same article, with M = L + (R - L)/2
- david_allison 4y agoI'm aware (plus the fact that the algorithm is correct in Python). It's very unlikely that this is an argument I can win. I'm taking a pragmatic perspective: like it or not, people are going to skim the article and copy & paste the pseudocode. Given that the pseudocode is buggy in the vast majority of programming languages and the user isn't informed about this in the pseudocode, it's going to lead to unnecessary bugs.
- enriquto 4y ago> people are going to skim the article and copy & paste the pseudocode. Heh. But then again, these kind of people will create way worse problems than last-bit overflows.
- elcomet 4y agoThey do discuss it though at the end of the article https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues https://en.wikipedia.org/wiki/Binary_search_algorithm#Implem... And as other mentionned, this is pseudo code and not implementation. But if you think it's incorrect, feel free to correct it.
- tromp 4y agoThe bug in question is trying to compute an average as avg = (x + y) / 2 which fails both for signed ints (when adding positive x and y overflows maxint) and for unsigned ints (when x + y wraps around 0). Note that this can only be considered a bug for array indices x,y when these are 32 bit variables and the array can conceivably grow to more than 2 billion elements. I wonder what is the simplest fix if the ordering between x and y is not known (e.g. in applications when x and y are not range bounds) and the language has no right-shift operation...
- deleted 4y ago[deleted]
- froh 4y agoM = L + (R - L)/2 looks fairly simple to me. note this works of any ordering of R and L if the data type is signed.
- mqus 4y agoBut doesn't this have the same overflow issue, e.g. if R is a large positive number and L is a large negative one?
- eesmith 4y agoIn binary search and heapsort, neither L nor R are negative - they are the number of elements in the array.
- Jensson 4y agoBinary search can be done on anything, not just arrays. Often you apply it to an algorithm and there isn't a collection at all, you just know the right answer is between some numbers so binary search lets you find it in logarithmic number of tries. If computing the number is costly then binary search is necessary to compute the result at all in those cases.
- blacklight 4y agoI'd put the blame on languages that don't allow exceptions, and whose return value in case of errors belong to the same domain as the solution. I've coded binary searches and sorts tons of times in C++, and yet none was succeptible to this bug. Why? Because, whenever you're talking indices, you should ALWAYS use unsigned int. Since an array can't have negative indices, if you use unsigned ints the problem is solved by design. And, if the element is not found, you throw an exception. Instead, in C you don't have exceptions, and you have to figure out creative ways for returning errors. errno-like statics work badly with concurrency. And doing something like int search(..., int* err), and setting err inside of your functions, feels cumbersome. So what does everyone do? Return a positive int if the index is found, or -1 otherwise. In other words, we artificially extend the domain of the solution just to include the error. We force into the signed integer domain something that was always supposed to be unsigned. This is the most common cause for most of the integer overflows problems out there.
- flupe 4y agoThe problem is not solved by using unsigned ints though, because it stems from integer overflow. I'm afraid your implementations are, alas, also incorrect.
- dataflow 4y agoConfused, how does using unsigned integers not solve this particular problem? Doesn't the article itself show solutions with unsigned integers?
- vintermann 4y agoOn mobile, this site is broken too. Text doesn't wrap and scrolling seems to be disabled.
- tiagod 4y agoI really dislike when devs disable mobile scrolling without knowing for sure their content is wrapping properly.
- rgovostes 4y agoIt's a post from before the iPhone came out, try reading the WAP version of the blog on your Cingular connection.
- remram 4y agoThe blog is still active though. Somehow they fixed their layouts but kept old posts on the old layout?
- andai 4y agoYeah I had to use reader mode.
- deleted 4y ago[deleted]
- delusional 4y agoCalling binary search and mergesort implementations "broken" does the author no service with his argument. If the key lesson is to "carefully consider your invariants" then the proper takeaway is that binary search and mergesort implementation lose generality with large arrays. The implementation shown works perfectly for arrays on the order 2^30. Calling them broken is like saying strlen is broken for strings that aren't null terminated.
- dataflow 4y agoI get what you're saying but I don't think they're analogous. If nothing else, strlen is defined only with null-terminated strings; this comes in both the spec itself, as well as the documentation of pretty much every implementation you find. Whereas most binary search implementations don't claim they only work under some particular inputs. (I think there are likely more differences too, but this is sufficient to make my point.) More generally, I feel like the thought process of "it's not broken if it works fine for inputs that occur 99% of the time" is an artifact of how little attention we pay to correctness, not something that is intrinsically true. If your function breaks for inputs that are clearly within its domain without any kind of warning... it's broken, as much as we might not want to admit it. We're just so used to this happening near edge cases that we don't think about it that way, but it's true.
- gnull 4y ago> most binary search implementations don't claim they only work under some particular inputs They do implicitly. It's just common sense. When you read a recipe in a cookbook, it usually doesn't mention that you're expected to be standing on your legs, not on your arms. Reader is expected to derive these things themselves. A lot of generic algorithm implementations will start acting weird if your input size has the order of INT_MAX. Instances this big will take days or weeks or process on commodity CPUs, so if you're doing something like that you would normally use a specialized library that takes these specifics into account.
- dataflow 4y ago
- EdSchouten 4y agoIf instead of 'int' you were to use 'size_t' (or the equivalent of that provided by your programming language of choice), then there should be no issues in practice. Then you would only see overflows if your elements were 1 byte in size, and the input spans more than half of the virtual address space. This is unlikely for two reasons: 1. If you only have single byte elements, you'd better use counting sort. 2. There always tend to be parts of the virtual address space that are reserved. On x86-64, most userspace processes can only access 2^47 bytes of space.
- deleted 4y ago[deleted]
- junon 4y ago> input spans more than half of the virtual address space Not only that, but in practice most general purpose operating systems are designed with higher-half kernels[0]. [0] https://wiki.osdev.org/Higher_Half_Kernel https://wiki.osdev.org/Higher_Half_Kernel
- valleyer 4y ago32-bit Mac OS X was not (it had a 4/4 scheme). Though even then I'm not sure you could reliably allocate two gigs of contiguous virtual space without running into some immovable OS-provided thing.
- deleted 4y ago[deleted]
- bugfix-66 4y agoHere is the approach taken in Go's sort.Search() Do the sum using signed int. Then cast to unsigned int before the division (i.e., use a non-arithmetic shift low). Then cast back to signed int. func Search(n int, f func(int) bool) int { // Define f(-1) == false and f(n) == true. // Invariant: f(i-1) == false, f(j) == true. i, j := 0, n for i < j { h := int(uint(i+j) >> 1) // avoid overflow when computing h // i ≤ h < j if !f(h) { i = h + 1 // preserves f(i-1) == false } else { j = h // preserves f(j) == true } } // i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i. return i } If you care about stuff like this you may enjoy the puzzle "Upside-Down Arithmetic Shift": https://bugfix-66.com/76b563beb6f4e61801fce4e835be862fb3dbbe08e75caaab80a495ed15a3e58b https://bugfix-66.com/76b563beb6f4e61801fce4e835be862fb3dbbe...
- morelisp 4y agoThe solution here is not really interesting except from a language design perspective. Go avoids this problem by having the maximum array length be int, but doing the math in uint. This won’t work in languages that lack uints (Java) or have maximum array sizes in uint (C/C++).
- LoganDark 4y agoJava lacks a distinct uint type, but (since Java 8) allows you to perform unsigned operations on a regular int, effectively treating it as a uint. It doesn't help that almost nobody knows this, though.
- morelisp 4y agoAt the point where you're writing `>>>` to, ironically, do proper arithmetic - you should probably write a correct version without a shift instead.
- wizeman 4y agoThis wouldn't work for C/C++ because in these languages signed integer overflow is undefined behavior.
- dataflow 4y agoFun fact, there are some other lessons here: it can sometimes pay off to (1) generalize your function, and (2) respect the mathematical axioms you're supposed to be following. This (obviously) isn't to say you should always generalize everything, but you should at least consider what would happen if you did so, and if the difference is small, perhaps do it. The benefit of doing so being that it can avoid problems that aren't otherwise obvious—sometimes by design, sometimes by accident. In particular, (x + y) / 2 is the wrong implementation of midpoint in general, because it would fail to even compile on objects you can't add together. But midpoint is well-defined on anything you can subtract (i.e. anything you can define a consistent distance function for)—and it doesn't require addition to be well-defined between those objects! One obvious (in C/C++, and not-so-obvious in Java) counterexample here is pointers/iterators. You can subtract them, but not add them. And, in fact, if you implement midpoint in a manner that generalizes to those and respects the intrinsic constraints of the problem, you end up with the same x + (y - x) / 2 implementation, which doesn't have this bug.
- morelisp 4y agoThis should also be obvious after a bit of thought to anyone who has worked with timestamps, and is also well-known in e.g. animation where midpoint is just a special case of p=0.5.
- europeanguy 4y agoInteresting. Another example is datetimes. You can't add datetimes. You can add a datetime and a time delta, and the difference of two datetimes is a timedelta. I guess in maths this is called a generating Lie algebra (maybe someone can comment on this?)
- maxiepoo 4y agoI think the concept you are looking for is a ["torsor"](https://en.wikipedia.org/wiki/Principal_homogeneous_space https://en.wikipedia.org/wiki/Principal_homogeneous_space). Basically, 1. You have a 0 time delta, and you can add and subtract them satisfying some natural equations. (time deltas form a group) 2. You can add time deltas to a datetime to get a new datetime, and this satisfies some natural equations relating to adding time deltas to each other (time deltas act on datetimes). 3. You can subtract two datetimes to get a time delta satisfying some more natural equations (the action is free and transitive).
- altaltalt 4y agoCan't it simply be written like this? mid = low/2 + high/2
- curling_grad 4y agoFor low=3, high=5 case, this gives mid=3.
- dataflow 4y agoNope, try low = 1, high = 1 and you get mid = 0.
- benmmurphy 4y agoi think you can fix it with: (low >> 1) + (high >> 1) + (low & 1 & high) for unsigned numbers. not sure if it works for signed numbers.
- deleted 4y ago[deleted]
- Godel_unicode 4y agoDivision is not associative: https://www.khanacademy.org/math/arithmetic-home/multiply-divide/properties-of-multiplication/a/associative-property-of-multiplication-review https://www.khanacademy.org/math/arithmetic-home/multiply-di...
- mimon 4y agoWhile that is true it is not relevant here, since this example does not involve associativity. What is relevent here is that integer division is not distributive over addition.
- lkuty 4y ago"It is not sufficient merely to prove a program correct; you have to test it too." Well in fact it is exactly the contrary.
- User23 4y agoIt’s a clumsy formulation, but if what he means is that you need to be assured that the model you’re proving in accurately reflects the behavior of what is being modeled then he is correct at least sometimes. For example a naive Z3 proof of the mid procedure would be valid since Z3 ints are unbounded. The issue isn’t that the proof is wrong, it’s that the model is. If the system has a well written formal specification then your model can be built from that without error if done diligently. One real world example is the first Algol 60 compiler, which was built to a formal specification. On the other hand if there is no useful spec or no spec at all then you end up needing to experiment, ie test, and get your model as close as you can.
- Jtsummers 4y agoI took it as a reference to Knuth: "Beware of bugs in the above code; I have only proved it correct, not tried it." https://staff.fnwi.uva.nl/p.vanemdeboas/knuthnote.pdf https://staff.fnwi.uva.nl/p.vanemdeboas/knuthnote.pdf [PDF] page 7 of the PDF, 5 of the classroom note.
- a1369209993 4y agoNo, what you've observed is the (IIRC the terminology) converse, namely: It is not sufficient merely to test a program; you have to prove it correct too. In addition, it is not sufficient merely to prove a program correct; you have to test it too. In summary, you have to both prove a program correct, and test it; skipping either will result in buggy garbage.
- joshuamorton 4y agoGrandparent is correct. If you've proven the behavior correct, you don't need to test. The proof is the test. This is usually only true in languages-that-are-proof-assistants (idris). In the cases above, they hadn't actually formally proven the behavior correct.
- queuebert 4y agoThis is a great example of how good algorithms are software plus hardware. The idea that a pure mathematical idea can be naively implemented on any hardware has never truly materialized. Yes, we are a long way from flipping switches to input machine code, but there are still hardware considerations for correctness and performance, e.g. the entire industry of deep learning running somewhat weird implementations of linear algebra to be fast on GPUs.
- dunhuang_nomad 4y agoDoes anyone know why the bitshift method works? Is it that low and high are both floating point, so you're not constrained by int precision and so you don't get an overflow error. The article makes it sound like sign switching is the issue, but this is just a general overflow problem, right?
- dataflow 4y agoThe ">>>" operator works, the ">>" operator doesn't. The reason the former works is that it basically performs unsigned division by a power of 2; the latter does it signed. There's no floating-point.
- erikpukinskis 4y agoWhat do the five >s and the , mean in this comment?
- dataflow 4y ago>>> is bitwise right shift (fills in with zeros), >> is arithmetic right shift (fills in with the sign bit).
- a1369209993 4y ago> >>> is bitwise right shift Well, they're both bitwise right shifts, the ">>>" is specifically a logical or unsigned right shift.
- dataflow 4y agoWhoops yes I meant logical.
- odo1242 4y agoNo, it's because the reason that integers overflow is that negative numbers are technically stored as larger than positive numbers in the Two's complement representation most computers use to store integers. Neither low and high are floats. Example with 8-bit integers (from wikipedia): Bits, Unsigned value, Signed value 0000 0000, 0, 0 0000 0001, 1, 1 0000 0010, 2, 2 0111 1110, 126, 126 0111 1111, 127, 127 1000 0000, 128, −128 When the logical bit shift is conducted on -128, -128 is treated as an unsigned integer. Its sign bit gets shifted such that the integer becomes 0100 0000, aka 64.
- jansan 4y agoSpoiler: If you are using Javascript, this bug only affects you if your arrays have more than Number.MAX_SAFE_INTEGER/2 entries, which is about 2^52. In other words, don't waste your time with fixing this bug.
- chowells 4y agoUnless you're binary searching something other than a data structure. Fascinatingly, binary search works just fine in optimization problems where the function to optimize is monotonic.
- dang 4y agoRelated: Google Research Blog: Nearly All Binary Searches and Mergesorts Are Broken - https://news.ycombinator.com/item?id=16890739 https://news.ycombinator.com/item?id=16890739 - April 2018 (1 comment) Nearly All Binary Searches and Mergesorts Are Broken (2006) - https://news.ycombinator.com/item?id=14906429 https://news.ycombinator.com/item?id=14906429 - Aug 2017 (86 comments) Nearly All Binary Searches and Mergesorts Are Broken (2006) - https://news.ycombinator.com/item?id=12147703 https://news.ycombinator.com/item?id=12147703 - July 2016 (35 comments) Nearly All Binary Searches and Mergesorts are Broken (2006) - https://news.ycombinator.com/item?id=9857392 https://news.ycombinator.com/item?id=9857392 - July 2015 (43 comments) Read All About It: Nearly All Binary Searches and Mergesorts Are Broken - https://news.ycombinator.com/item?id=9113001 https://news.ycombinator.com/item?id=9113001 - Feb 2015 (2 comments) Nearly All Binary Searches and Mergesorts are Broken (2006) - https://news.ycombinator.com/item?id=7594625 https://news.ycombinator.com/item?id=7594625 - April 2014 (2 comments) Nearly All Binary Searches and Mergesorts are Broken (2006) - https://news.ycombinator.com/item?id=6799336 https://news.ycombinator.com/item?id=6799336 - Nov 2013 (46 comments) Nearly All Binary Searches and Mergesorts are Broken (2006) - https://news.ycombinator.com/item?id=1130463 https://news.ycombinator.com/item?id=1130463 - Feb 2010 (49 comments) Google Research Blog: Nearly All Binary Searches and Mergesorts are Broken [2006] - https://news.ycombinator.com/item?id=621557 https://news.ycombinator.com/item?id=621557 - May 2009 (9 comments)
- utopcell 4y ago
- Jtsummers 4y agoYou may want to read the FAQ: > Are reposts ok? > If a story has not had significant attention in the last year or so, a small number of reposts is ok. Otherwise we bury reposts as duplicates. Note that the most recent prior posting was several years ago so easily fits within the FAQ's description of what's ok.
- dang 4y agoRight! The purpose of 'related' lists is simply to give people more (hopefully) interesting threads to read.
- GuB-42 4y agoIt is unfortunate that the language doesn't have a built-in "average between two ints" function. It is a common operation, people often get it wrong, as shown by this article, and it may have a really simple and correct assembly representation that the compiler may take advantage of. Such a function, even if it seems trivial, has some educative value as it opens an opportunity to explain the problem in the documentation.
- fay59 4y agoI feel that it’s so simple that many people will overlook that it even exists. In languages that have both, it’s hard for functions to compete with operators. I don’t think that this is the best design to promote correctness.
- GuB-42 4y agoMaybe, but providing simple functions for "obvious" operations, to promote correctness, make it easier for the compiler, or just for convenience is not uncommon at all. Most languages have a min/max function somewhere, sometimes built-in, sometimes in the standard library, even though it is trivial to implement. C is a notable exception, and it is a problem because, you have a lot of ad-hoc solutions, all with their own issues. If you look at GLSL, it has many function that do obvious things, like exp2(x) that does the same thing as pow(2,x), and I don't think anyone has any issue with that. It even has a specific "fma" operation (fma(a,b,c) = a*b+c, precisely), that solves a similar kind of problem as the overflowing average.
- User23 4y agoKnuth’s section on binary search in The Art of Computer Programming is enlightening. One historical curiosity that he notes is that it took something like a decade from the discovery of the algorithm to an implementation that was correct for all inputs. I briefly tried using binary search as a weeder problem and quickly abandoned it when no one got it right.
- fnordpiglet 4y agoThis was always my go to interview question when I wanted to smugly prove to someone I’m smarter than them because I knew in fact they were smarter than me and I was feeling insecure. Good to see others use overflow gotchas too.
- junon 4y agoI hate when interviewers rely on niche recall-only interview questions...
- latency-guy2 4y agoEh, I don't think integer overflow is a recall-only type question This type of issue is pretty common to encounter and I make at least a few fixes a year specifically addressing integer overflow across many companies
- 0x445442 4y agoMy favorite was; write a function that determines the number of games necessary to be played in a single elimination tournament with N participants. It’s interesting to watch how many go off into recursion land when they get into the mind set of solving these Leet Code puzzles.
- quag 4y agoN-1 games?
- fnordpiglet 4y agoMy favorite is when interviewers expect you to know sportsball stuff like tournament elimination rules when interviewing programmers who clearly don’t care about sportsball
- 0x445442 4y agoCould be chess.
- kfajdsl 4y agoMy data structures professor took off points for that in an assignment once :(
- IncRnd 4y agoThere are still edge cases here - various posters here have mentioned them. The proper method is to type promote first - not just to unsigned but to a wider variable type - 32 to 64 bits or from 64 to 128 bits. Unsigned simply gives a single extra bit, while erasing negative semantics. Promoting to twice the size works for either addition or multiplication. The benefits are correctness and the ability to be understood at a glance.
- dataflow 4y ago> There are still edge cases here - various posters here have mentioned them. Are you sure? What's an example of an array.length that would trigger a remaining edge case here? (Keep in mind array.length is 32-bit in Java.)
- deleted 4y ago[deleted]
- legosexmagic 4y agothe right solution is to parametrize the search region as (offset, length) instead of (start, end). then the midpoint is just offset+length/2. you can also remove that unpredictable branch in the loop if you want. whatever_t *bisect(whatever_t *offset, size_t length, whatever_t x) { while(size_t midpoint = length / 2) { bool side = x < offset[midpoint]; midpoint &= side - 1; length >>= side; offset += midpoint; length -= midpoint; } return offset; }
- abecedarius 4y ago(offset, length) was how I coded it in the 90s, too, precisely because it made correctness clearer. "Nearly all" broken, hmph.
- runeblaze 4y agoOh boy, in 2022 you could not afford writing a broken binary search in any serious coding interview. Back before 2006 apparently PhD students in CMU could not.
- feoren 4y agoAre you kidding? If you were asked in a coding interview to write a binary search, and you wrote the broken version in the post on a whiteboard, you'd be in the top 5% of applicants. Most applicants can barely write a for loop on the board.
- butlerm 4y agoAnyone dealing with arrays containing a billion elements or more really ought to be using 64 bit arithmetic to avoid problems like this. Certainly better to do this the right way though.
- PartiallyTyped 4y agoIs there any reason not to use 64bit arithmetic anyway?
- seanp2k2 4y ago
- verall 4y agoSame thing on a (Google) Pixel 6 Pro :P
- cpcallen 4y agoMy older iPhone SE has a screen small enough that even that did not suffice . :-(
- Traubenfuchs 4y agoI went for the reader mode, but I wonder how things end up like this. Was the css written on a desktop and not once tested on iOS?
- kelnos 4y agoPlease don't bother with posts like this. They don't add anything useful to discussion, and are against site guidelines: > Please don't complain about tangential annoyances—e.g. article or website formats, name collisions, or back-button breakage. They're too common to be interesting.
- kazinator 4y agoThis article is poorly/incompletely reasoned. Suppose your high, low and mid indexes are as wide as a pointer on your machine: 32 or 64 bits. Unsigned. Suppose you're binary searching or merge sorting a structure that fits entirely into memory. The only way (low + high)/2 will overflow is if the object being subdivided fills the entire address space, and is an array of individual bytes. Or else is a sparsely populated, virtual structure. If the space contains distinct objects from [0] to [high-1], and they are more than a byte wide, this is a non-issue. If the objects are more than two bytes wide, you can use signed integers. Also, you're never going to manipulate objects that fill the whole address space. On 32 bits, some applications came close. On 64 bits, people are using the top 16 bits of a pointer for a tag.
- kragen 4y ago> Suppose your high, low and mid indexes are as wide as a pointer on your machine: 32 or 64 bits. Unsigned. Yeah, if you suppose that, you can correctly conclude that you only run into overflow if the object is a byte array that fills more than half the address space (though not the entire address space as you say). And that's why this problem remained unnoticed from 01958 or whenever someone first published a correct-on-my-machine binary search until 02006. But suppose they aren't. Suppose, for example, that you're in Java, where there's no such thing as an unsigned type, and where ints are 32 bits even on a 64-bit machine. Suddenly the move to 64-bit machines around 02006 demonstrates that you have this problem on any array with more than 2³⁰ elements. It's easy to have 2³⁰ elements on a 64-bit machine! Even if they aren't bytes.
- deleted 4y ago[deleted]
- yarskegg 4y agoI think this might be better for c/c++ though admittedly a bit more cryptic: (x>>1) + (y>>1) + (0x01 & x & y)