Nearly All Binary Searches and Mergesorts Are Broken (2006)

Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by flupe on Sunday November 06, 2022 @09:13AM (#33492825)

The problem is not solved by using unsigned ints though, because it stems from integer overflow. I'm afraid your implementations are, alas, also incorrect.

[ Parent | on HN ]

Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by dataflow on Sunday November 06, 2022 @10:10AM (#33493413)

Confused, how does using unsigned integers not solve this particular problem? Doesn't the article itself show solutions with unsigned integers?

[ Parent | on HN ]

Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by Filligree on Sunday November 06, 2022 @10:22AM (#33493553)

Unsigned int is 32-bit, most address spaces are 48-bit or more.

[ Parent | on HN ]

Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by dataflow on Sunday November 06, 2022 @10:24AM (#33493578)

Array.length is 32-bit in Java. This is from 2006.

[ Parent | on HN ]

Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by a1369209993 on Sunday November 06, 2022 @04:55PM (#33497750)

Example using 16-bit size_t for convenience:

  char array[60000]; // 5KB left for code and stack if not segmented
  size_t i = 40000;
  size_t j = 50000;
  size_t mid = (i+j)/2; // should be 45000
  // i+j = (size_t)90000 = 24464
  // mid = 24464/2 = 12232 != 45000

Larger integers make the necessary array size bigger, but don't change the overall issue.

[ Parent | on HN ]