Nearly All Binary Searches and Mergesorts Are Broken (2006)
research.googleblog.com
Nearly All Binary Searches and Mergesorts Are Broken (2006)
1–10 of 95 posts
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#2That 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.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#3That 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.
Agreed completely; the right fix is that anything indexing an array should be an unsigned size_t (or equivalent for your language of choice).
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#4I 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 it be possible to predict?
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#5I 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.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#6That 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.
For C99, the correct type for an array index is size_t. unsigned int isn't guaranteed to be big enough, while size_t is guaranteed to be large enough for the target architecture.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#7I 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.
[deleted]
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#8The bug isn't in your algorithm; the bug is in your language, which doesn't provide arbitrary-precision integer arithmetic by default.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#9[deleted]
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#10That 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.
Agreed completely; the right fix is that anything indexing an array should be an unsigned size_t (or equivalent for your language of choice).
Simply changing to size_t doesn't really fix this bug. You still have to use the low + (high - low) / 2 fix.