有偏二进制排序返回插入的第一个索引

Question

我正在尝试一种方法返回第一个可能的位置我可以在递增列表中插入一个新项。我的一般尝试是使用二叉排序，直到出现以下情况:前一项小于插入项，下一项等于或大于插入项:

lis = [1,1,2,2,2,4,5,6,7,8,9]
def binary_sort(elem, lis, left, right):
mid = (left + right)//2
if (lis[mid-1] < elem and elem <= lis[mid]):
return mid
elif (lis[mid] > mid):
return binary_sort(elem, lis, mid, right)
else:
return binary_sort(elem, lis, left, mid)

这是不工作…我的代码或总体策略的问题在哪里?

Answer 1

我建议看一下下面的代码。

def binary_insertion_search(elem, items, left, right):
if elem > items[right]:
return right + 1
while left < right:
mid = (left + right) // 2
if elem > items[mid]:
left = mid + 1
elif elem <= items[mid]:
right = mid
return left

我稍微重写了一下你的函数。下面是解释:

我假设要返回的索引是任何内容可以放置的第一个位置，这反过来会将后面的所有项向右移动。

由于设计上不能将索引合并到列表范围之外，因此必须检查元素是否大于列表末尾的项。然后返回下一个可能的索引len(lis)。

为了避免递归，我使用了while循环。首先，我们检查left是否等于或大于right。

你计算的mid值很好，所以我就保留它。

如果元素大于mid的项，则唯一可能的下一个选项是选择下一个未检查位置，即mid + 1。

现在是有趣的部分。像在另一种情况下一样，为了找到最左边的项，我们必须将right的边界设置为mid - 1，以便跳过mid元素。但是，我们检查元素是小于还是等于到mid的项目。这保证了当我们找到一个与搜索元素相等的候选元素时，我们再次运行搜索(从右开始缩小范围)，以可能找到一个更小的索引。当left == right为true时，循环结束。

我希望这能回答你的问题，并指出代码中的差异!