I don't think that is broken. The algorithm is sound conceptually. I was almost looking for some type of theory where all mergesorts and binary searches could be improved.
Nearly All Binary Searches and Mergesorts Are Broken (2006)
11–20 of 95 posts
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#12I wish it was worth a lot to be good at systems programming these days. It seems like the huge salaries are for rails senior devs. I spent like ten years getting really good at this stuff (the (low + high)/2 line jumped right out at me) but nowadays it feels like being really good at trivial pursuit. It's interesting how much things have changed in the last decade. I wonder what next decade's "Rails" will be? Could i…
I wish it was worth a lot to be good at assembly these days. It seems like the huge salaries are for c++ devs. I spent like ten years getting really good at this stuff but nowadays it feels like being really good at trivial pursuit. Edit: Did not mean to "mock" the OP, just merely trying to showing that you can apply that thought to almost anything in the programming world by replacing the technology/language names.
Are you mocking the parent poster? Why?
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#13Earlier quoted context omitted.
I wish it was worth a lot to be good at assembly these days. It seems like the huge salaries are for c++ devs. I spent like ten years getting really good at this stuff but nowadays it feels like being really good at trivial pursuit. Edit: Did not mean to "mock" the OP, just merely trying to showing that you can apply that thought to almost anything in the programming world by replacing the technology/language names.
Are you mocking the parent poster? Why?
Nah, I thought it was a good point. It's easy to forget that we either change or become obsolete. It's one thing to know it abstractly, but it's hard to make any lifestyle changes, especially if it involves switching to a job in a completely new domain.
http://thecodist.com/article/the_programming_steamroller_wai... is a good essay on this.
EDIT: previous discussion: https://news.ycombinator.com/item?id=7204515
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#14That line from the C/C++ "fix" is an atrocity; `low`, `mid`, and `high` should never have been declared as signed integers in the first place, since array indices are never negative. It's unfortunate that in Java there is no other option than to use signed ints.
Even with unsigned int (or even size_t), the C/C++ code still doesn't sit well with me. The addition can still overflow, and while unsigned overflow is well-defined, the result here is still nonsense. (i.e., while the result of (low + high) >> 1 during overflow will be well defined, it won't be the midpoint…)
You might argue that you're never going to overflow a size_t on a 64-bit, maybe, but given that the correct code is right there above in the article, it seems easy enough to just do the right thing (add half the delta to the lower bound, which avoids overflow all together for unsigned integer inputs).
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#15* for arrays with counts over a billion if you choose to use signed 32-bit integers for array indexes.
Not that it isn't a potential problem, but it's a narrow issue.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#16The bug isn't in your algorithm; the bug is in your language, which doesn't provide arbitrary-precision integer arithmetic by default.
Big integer by default is a terrible idea. Just look at Python 3.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#17I wish it was worth a lot to be good at systems programming these days. It seems like the huge salaries are for rails senior devs. I spent like ten years getting really good at this stuff (the (low + high)/2 line jumped right out at me) but nowadays it feels like being really good at trivial pursuit. It's interesting how much things have changed in the last decade. I wonder what next decade's "Rails" will be? Could i…
It's still worth a lot to be good at systems programming. Outside of the HN bubble there are plenty of companies willing to pay extremely well for people who can do systems programming, particularly under high performance constraints.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#18The bug isn't in your algorithm; the bug is in your language, which doesn't provide arbitrary-precision integer arithmetic by default.
Big integer by default is a terrible idea. Just look at Python 3.
Python 2 was bigint by default. Not even going to deconstruct your argument past that
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#19Earlier quoted context omitted.
Are you mocking the parent poster? Why?
Nah, I thought it was a good point. It's easy to forget that we either change or become obsolete. It's one thing to know it abstractly, but it's hard to make any lifestyle changes, especially if it involves switching to a job in a completely new domain. http://thecodist.com/article/the_programming_steamroller_wai... is a good essay on this. EDIT: previous discussion: https://news.ycombinator.com/item?id=7204515
That's an amazing article. Thanks for sharing.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#20The bug isn't in your algorithm; the bug is in your language, which doesn't provide arbitrary-precision integer arithmetic by default.
Erlang has arbitrary length integers by default, and I've found it to be incredibly liberating.