The way bsearch() computes indices is subject to integer overflow. This should be only a problem on 32-bit systems, where it's possible to allocate more than SIZE_MAX/2 bytes of memory. The attached patch should fix this bug, but it was only lightly tested. I also attached test case, which currently loops forever on 32-bit systems. (Beware that it allocates 3GB of memory. Don't run it on a system that is short of RAM!)