(High-low) works, well if we consider this from a pointer pov!
Nearly All Binary Searches and Mergesorts Are Broken (2006)
61–70 of 95 posts
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#62Earlier quoted context omitted.
Name 5 please
google facebook microsoft amazon baidu
All of those places will pay just as much for (as well as hire far more of) enterprise Java/Go/HTML/JS code monkeys There's nothing wrong with that, but picking 5 companies with their hands in damn-near anything is disingenuous.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#63Won't this line have similar issue?
return -(low + 1); // key not found.Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#64Previous discussions at https://hn.algolia.com/?query=Nearly%20All%20Binary%20Search...
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#65Earlier quoted context omitted.
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.
Name 5 please
ng nasa boeing lockheed spacex
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#66Earlier quoted context omitted.
google facebook microsoft amazon baidu
All of those places will pay just as much for (as well as hire far more of) enterprise Java/Go/HTML/JS code monkeys There's nothing wrong with that, but picking 5 companies with their hands in damn-near anything is disingenuous.
Is your goal to be paid extremely well for doing systems programming relative to other people in the same company? Or to be paid extremely well for doing systems programming?
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#67That 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.
> size_t is guaranteed to be large enough for the target architecture
I'm not sure if you've misunderstood this (some of the other comments mentioning type certainly have) but size_t being large enough for the purpose of indexing an array is absolutely not the issue. The issue, illustrated by the glibc code pishpash shared, is that a size_t (or any other integer type) is not necessarily large enough to hold the sum of two other variables of the same type without overflowing.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#68Earlier quoted context omitted.
Right, but a generalization of discrimination-based sorts didn't exist until earlier this decade. So it was a reasonable statement to misinterpret or relegate to "say you have a 30m character string you wanted to sort as quickly as possible" interview questions. I certainly didn't realize how generalized discrimination-based sorts were. Many people I've talked to outside of the Haskell community don't know at all. I'…
Huh, is this the stuff you're talking about: http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011c.pdf https://www.youtube.com/watch?v=sz9ZlZIRDAg https://hackage.haskell.org/package/discrimination I didn't know about this until I read your reply and googled; I thought you were just obliquely referring to radix sort or something l…
Yes that is it. And it's really a variation on radix sort as well. They're all in the same general family.
I can't believe I got down voted for this thread. What does it take?
I guess I should just post it.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#69Earlier quoted context omitted.
Right, but a generalization of discrimination-based sorts didn't exist until earlier this decade. So it was a reasonable statement to misinterpret or relegate to "say you have a 30m character string you wanted to sort as quickly as possible" interview questions. I certainly didn't realize how generalized discrimination-based sorts were. Many people I've talked to outside of the Haskell community don't know at all. I'…
Huh, is this the stuff you're talking about: http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011c.pdf https://www.youtube.com/watch?v=sz9ZlZIRDAg https://hackage.haskell.org/package/discrimination I didn't know about this until I read your reply and googled; I thought you were just obliquely referring to radix sort or something l…
[deleted]
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#70So what 'bout this? It's the latest glibc. https://fossies.org/dox/glibc-2.25/stdlib-bsearch_8h_source....
The problematic line is: __idx = (__l + __u) / 2; __idx, __l, and __u are all the same type and the addition of __l and __u could cause an overflow resulting in a nonsense value assigned to __idx.
Seems like it's still an open ticket: