[kragen]

And in fact finding the midpoint is not possible half the time in the space we're interested in (https://news.ycombinator.com/edit?id=33497270). So what is the algebraic structure that underlies the binary-search algorithm, since evidently it isn't really the torsor of a group?

[JadeNB]

> So what is the algebraic structure that underlies the binary-search algorithm, since evidently it isn't really the torsor of a group?

Though it pains me to say so as an algebraist, I think that it probably just isn't a problem most usefully modelled with a more abstract algebraic structure. Although it would be easy to cook up a structure permitting "division with rounding" … maybe a Euclidean domain (https://en.wikipedia.org/wiki/Euclidean_domain) is something like the right structure?

[kragen]

I'm not an algebraist! So maybe what I'm about to say is dumb:

As I understand it, the correctness of any correct algorithm is conditioned on some requirements about the data types it's operating on and the operations applicable to it. Once you formalize that set of requirements, you can apply the algorithm (correctly) to any data type whose operations fulfill them.

But some sets of data and some operations on them that fulfill some formally stated requirements are just an abstract algebra, aren't they? Like, if you have two data types {F, V} and operations on them {+, ×, ·, +⃗} that fulfill the vector-space axioms, they're a vector space, so any vector-space algorithm will work on them. So every algorithm (or, more accurately, every theorem about an algorithm) defines some algebraic structure (or several of them), which may or may not be a well-known one.

For binary search you have two sets: the set of indices I, which is what we've been talking about, and the set E of elements that might occur in the array a you're searching through. You need a total order on E, and I think you need a total order on I, and the array a needs to be sorted such that aᵢ ≤ aⱼ if i < j (though not conversely, since it might contain duplicates). You need a midpoint operation mid(i, j) to compute a new index from any two existing indices such that i ≤ mid(i, j) < j if i < j. And "mid" needs a sort of well-foundedness property on I to guarantee that the recursion eventually terminates; for any subset of ℤ you can define a "mid" that fulfills this, but for example in ℚ or ℝ you cannot, at least not with the usual ordering.

I don't think a Euclidean domain is quite the right thing for I because there's no obvious total order, and I think you need a total order to state the sortedness precondition on the array contents. Also, lots of Euclidean domains (like ℚ or ℝ) are dense and therefore could lead you to nonterminating recursion. And it isn't obvious to me that "mid" requires so much structure from I.

If you care about complexity you also have to define the cost of operations like ≤, mid, and array indexing, so your algorithm is no longer defined on just an abstract algebra, but an abstract algebra augmented with a cost model. But for correctness and termination that isn't required.

[hither_shores]

> But some sets of data and some operations on them that fulfill some formally stated requirements are just an abstract algebra, aren't they?

Not quite. A variety of algebras (which is usually what people have in mind when they talk about "algebraic structures" in general) is a collection of operations with equational laws, meaning that they're of the form "for all x_0, x_1, ... (however many variables you need), expression_1(x_0, x_1, ...) = expression_2(x_0, x_1, ...)", where the expressions are built up out of your operators.

Fields are the classic example of a structure studied by algebraists which is nonetheless not a variety of algebras: division isn't described by equational laws, because it's defined for everything except zero. This makes fields much harder to work with than e.g. groups or rings, in both math and programming.

[kragen]

Interesting, I never realized that fields weren't algebras!

[JadeNB]

> Interesting, I never realized that fields weren't algebras!

One has to be quite careful with the terminology when crossing disciplines, as here. Fields are, rather boringly, algebras over themselves, in what I dare to call the ‘usual’ sense of an algebra over a field (https://en.wikipedia.org/wiki/Algebra_over_a_field). Rather what hither_shores is saying is that the collection of fields does not form a variety of algebras, in the sense of universal algebra https://en.wikipedia.org/wiki/Variety_(universal_algebra) (which is itself quite different from the algebraic-geometry sense https://en.wikipedia.org/wiki/Algebraic_variety). See, for example, https://math.stackexchange.com/questions/3756136/why-is-the-... .

[kragen]

Ouch! Thanks for clarifying (at least, I hope it will turn out to be clarifying after I read some more...)

[JadeNB]

> I don't think a Euclidean domain is quite the right thing for I because there's no obvious total order, and I think you need a total order to state the sortedness precondition on the array contents. Also, lots of Euclidean domains (like ℚ or ℝ) are dense and therefore could lead you to nonterminating recursion. And it isn't obvious to me that "mid" requires so much structure from I.

I think you may be confusing integral domains (https://en.wikipedia.org/wiki/Integral_domain) with Euclidean domains (https://en.wikipedia.org/wiki/Euclidean_domain). Although any field is a Euclidean domain, the structure is not very useful (what I am used to calling the norm, but Wikipedia calls the Euclidean function, may be taken to be identically 0, and the remainder from every division may also be taken to be 0). But anyway, I was just free associating (no pun (https://en.wikipedia.org/wiki/Associative_property) intended).

I certainly agree that one can create a structure that encodes the algebra of binary search, and, at a casual glance, your definition looks good to me. I meant only that such a structure seems unlikely to do much more than to encode binary search (unlike, say, affine spaces, which are useful in a very broad variety of settings for which they have not been purpose-built) … although of course any mathematical structure, howsoever abstract or specialised, will find other uses if enough people get interested in it.

[kragen]

well, it'd be nice if it turned out that it was a consequence of some other well-known structure that was more general than just 'subsets of the integers'. but maybe it isn't.