Talk:Uniform binary search

C implementation

[redacted wrong code; see page history for details --Quuxplusone 06:35, 27 September 2006 (UTC)]

Note that this code has a tough time with arrays that have an even number of elements ... I found you need to put 'sentinel' entries that are max-value at the end. I suspect the code wasn't translated quite right from the original MIX code in Dr. Knuth's book. —The preceding unsigned comment was added by Gnewf (talk • contribs) .

You are absolutely right. I can't believe I didn't test that code thoroughly before adding it. Apologies. A corrected and tested version has been posted now. (And with a main that shows the proper usage, unlike that cruft someone else put up without testing either. Hey, at least I don't make mistakes like "void main"! I make big complicated mistakes! :) --Quuxplusone 06:35, 27 September 2006 (UTC)

Implementation Safety

I believe there may be errors in the current implementation on the page, specifically relating to array bounds. I tested the code on OnlineGDB and it resulted in two out-of-bounds accesses:

1. In the make_delta function, 0 is written to delta[4], but delta is only 4 entries wide (index goes up to 3)
2. In the unisearch function, when searching for the number 0 the key == a[i] check accesses a[-1]

In the C implementation used by OnlineGDB neither of these caused crashes or issues (arrays are seemingly given a sort of buffer of zeroes), but I believe this is considered implementation-defined behavior and thus can not be relied upon on other C runtimes. DoryL-36 (talk) 02:17, 12 August 2023 (UTC)