Pigeon函数：将x插入到排序列表中的位置
假设我有一个排序的事物列表
{thing1, thing2, thing3, ...}
和一个二进制比较函数，该函数表示一个事物是否应该按该排序顺序出现在另一个事物之前。 （我说“事物”是因为它们不必是数字；它们可以是任意数据结构。）
我现在寻找一个函数，它接受
- 事物的排序列表、
- 比较函数和
- 一个事物
，并返回中的第一对相邻事物应在其间插入新事物的列表。 也就是说，返回第一个相邻对 {a,b}，使得 comp(a,x) 和 comp(x,b) 为 true，其中 comp() 是比较函数。
例如，
pigeon[{1,3,5,7}, Less, 4]
应该返回
{3,5}
(编辑：如果给定的事物小于列表的第一个元素 a，则返回 {Null, a}。同样，如果它大于最后一个元素 z，则返回 {z,此外，我们需要假设比较函数对于两个相同的元素返回 true（即，它类似于 LessEqual 而不是 Less），或者由于高性能标记，事物列表不包含被标记的事物。 我的第一个想法
是使用 Split，然后分别获取结果两个子列表的 Last 和 First。 我会将其作为答案发布（或者随意击败我），但我想有一种更有效或更优雅的方式。
Suppose I have a sorted list of things
{thing1, thing2, thing3, ...}
and a binary comparison function that says whether one thing should come before another in that sort order. (I say "things" because they need not be numbers; they can be arbitrary data structures.)
I now seek a function that takes
- a sorted list of things,
- a comparison function, and
- a thing
and returns the first pair of adjacent things in the list that the new thing should be inserted between.
That is, return the first adjacent pair {a,b} such that comp(a,x) and comp(x,b) are true, where comp() is the comparison function.
For example,
pigeon[{1,3,5,7}, Less, 4]
should return
{3,5}
(EDIT: If the given thing is less than the first element, a, of the list, then return {Null, a}. Likewise, if it's greater than the last element, z, then return {z, Null}. Additionally, we need to either assume that the comparison function returns true for two identical elements (ie, it's like LessEqual rather than Less) or that the list of things doesn't contain the thing being pigeoned. Thanks to High Performance Mark for catching that!)
My first thought was to use Split and then take the Last and First, respectively, of the resulting two sublists.
I'll post that as an answer (or feel free to beat me to it) but I imagine there's a more efficient or elegant way.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
使用 BinarySearch
假设：列表中没有重复的元素。
BinarySearch 有另一种形式：
如果您的列表按上述“f”的结果排序，则可以使用该形式。
Using BinarySearch
Assumption: No repeated elements in list.
BinarySearch has an alternative form:
which may be used if your list is sorted by the results of the aforementioned "f".
我认为这是一个很好的解决方案：
给出：
解释：Piecewise函数在BinarySearch内部应用于列表{1,3,5,7}，以检查哪些元素LessEqual，BinarySearch比找到该标记的末尾位置，并返回相关元素。此实现仅使用 BinarySearch，因此它应该非常有效。
这个函数可以很容易地更改为在第二种情况下返回 {1, 3}。
或者，如果“x”可以是“list”的元素，则类似以下内容：
将给出：
I think this is a good solution:
giving:
Explanation: the Piecewise function is applied inside the BinarySearch to the list {1, 3, 5, 7}, to check which elements are LessEqual, the BinarySearch than finds the position of the end of this mark, and the relevant elements are returned. This implementation uses only BinarySearch, so it suppose to be quite efficient.
This function can be easily changed to return in the second case {1, 3} instead.
Alternatively, if 'x' can be an element of 'list', something like this:
will give:
已经晚了，所以这里是部分指定函数的部分解决方案：
我冒昧地不要求对提供给函数
f的列表进行排序，因为输入参数包括比较函数。只要 (a) 元素el不是l的成员并且 (b)l中存在已排序的元素，此函数就可以正常工作位于el的左侧和右侧。它可能不适用于LessEqual或GreaterEqual。如果您愿意澄清当 (a) 和 (b) 中的一个或两个不满足时您希望函数返回什么，我很乐意在早上再次查看这个问题。
编辑：
我认为这满足了修订后的要求。和以前一样，它不需要输入列表已经排序。
我将让其他人来判断这个解决方案的优雅和效率（我可以看到在后一方面有一些明显的改进）。现在要回去工作了。
It's late, so here's a partial solution to a partially specified function:
I've taken the liberty of not requiring that the list supplied to the function
fbe sorted, since the input arguments include the comparison function. This function works well as long as (a) the elementelis not a member ofland (b) there are elements inlsorted to both left and right ofel. It probably doesn't work forLessEqualorGreaterEqualeither.If you care to clarify what you'd like the function to return when either or both of (a) and (b) is not met, I'll be happy to have another look at this in the morning.
EDIT:
I think this satisfies the revised requirements. As before, it doesn't require that the input list be already sorted.
I'll leave it to others to judge the elegance and efficiency of this solution (I can see some obvious improvements in the latter respect). Now to get back to work.
一种可能的方法：
Output = {3, 5}
或者，可以用 SplitBy 代替 GatherBy。
One possible approach:
Output = {3, 5}
Alternatively, SplitBy may be substituted for GatherBy.
下面是一个使用 Select（注意第三个参数）的解决方案，它最多遍历列表一次，在找到鸽子洞时停止：
示例：
Here's a solution using Select (note the third argument) that takes at most one pass through the list, stopping when it finds the pigeonhole:
Examples:
这是另一个二分搜索答案：
我这样尝试：
它与我的另一个答案（带有 Select 的答案）相匹配，但速度要快得多。
其他例子：
Here's another binary search answer:
I tried it like this:
That matches my other answer (the one with Select) but is much faster.
Other examples: