sorting - 鸽子函数: where to insert x into a sorted list

Question

假设我有一个排序的列表

{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, Null} .此外，我们需要假设比较函数对于两个相同的元素返回 true(即，它类似于 LessEqual 而不是 Less)，或者事物列表不包含被鸽子的事物。感谢 High Performance Mark 捕获那个!)

我的第一个想法是使用 Split，然后分别获取结果两个子列表的 Last 和 First。我会将其作为答案发布(或者随意击败我)，但我想有一种更有效或更优雅的方式。

Answer 1

使用二进制搜索

假设:列表中没有重复的元素。

BinarySearch 有另一种形式:

BinarySearch[l,k,f]
gives the position of k in the list obtained from l by applying f to 
each element in l.  

如果您的列表是按上述“f”的结果排序的，则可以使用它。

Clear["Global`*"]; Needs["Combinatorica`"];
ret[list_, f_, elem_] := Module[{pos, last},
  pos[l_, e_, g_] := IntegerPart[BinarySearch[l, g[e], g]];
  {
   list[[pos[list, elem, f]]] /. List -> Null,
   If[(last = pos[list, elem, f] + 1) > Length@list, Null, list[[last]]]
  }
 ]  

a = {1, 2, 3, 4, 5};
b = SelectionSort[a, Cos[#1] < Cos[#2] &]

{3, 4, 2, 5, 1}  

Table[{x, N[Cos[x], 2], ret[b, Cos, x]}, 
     {x, 1, 6}]  

{{1,  0.54, {1, Null}}, 
 {2, -0.42, {2, 5}}, 
 {3, -0.99, {3, 4}}, 
 {4, -0.65, {4, 2}}, 
 {5,  0.28, {5, 1}}, 
 {6,  0.96, {1, Null}}
}  

ret[b, Cos, Pi]  
{Null, 3}