There are serious issues with the original paper

[luc0x61]

Now, the original paper is at first appealing, but on a complete read is really appalling.

The first thing I noted were wild discrepancies in the claimed running times.
Then I found this implementation and a simpler derived algorithm in Black-White-Array, which bears almost all the defects of the original paper.
If you're using the original algorithm described for items deletion your code can't work, as it is screwed. The original author described even a totally wrong basic binary search algorithm(!). Although, even a correct one can't work in there - a basic example is from page 7, fig. 3(a); try a binary search for number '6' in the given data set: it will fail, because of the 'VOID' markers described on the same page.

The original paper is deeply embarrassing, I don't think it's worth mentioning as the base of any real development (unless with a big disclaimer).
Since it's too old, it's not even LLM slop, but I can't say how good or bad is this.

[dronnix]

Hey, @luc0x61 🤝

Although, even a correct one can't work in there - a basic example is from page 7, fig. 3(a); try a binary search for number '6' in the given data set: it will fail, because of the 'VOID' markers described on the same page.

That's a right observation 👍 To address this problem, I mark the element as deleted at a separate bool array and this invariant, instead of VOID. Also this situation is covered in tests.

The original paper is deeply embarrassing, I don't think it's worth mentioning as the base of any real development (unless with a big disclaimer).

It reflects the basic idea and pays respect to the author 🙏 @bufistov is working on a clearer and comprehensive description.