Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col...
by Asooka on Friday October 20, 2017 @02:16AM
(#15513830)
The article keeps mentioning sorted sets, which is slightly confusing, because I am familiar with sets being defined, both in math and every programming language I know, as unordered. Is set in OCaml an ordered collection usually?
[ Parent
| on HN ]
Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col...
by a-nikolaev on Friday October 20, 2017 @03:06AM
(#15514012)
The article mentions word "set" only in the statement of the problem. And even in that statement it's made clear that the choice of words is intentional, because the underlying data structure is not specified, so it doesn't have to be an array immediately.
Ordered collection != sorted collection, btw. Sorted collections are actually more like sets than like arrays. A data structure that stores the elements in a sorted fashion is actually able to store an unordered collection with naturally defined insertion / deletion operations. (In OCaml, Set data structure is represented as a balanced binary tree, for instance, and it requires an order relation defined for its elements.)
Re:Pearl No. 4 – Kth Smallest in the Union of Two Sorted Col...
by jacksontale on Friday October 20, 2017 @04:19AM
(#15514282)
Sorry for the confusion. You are absolutely right. I just copy/paste the original problem statement in the book.
Will change