偏二分排序 Return 第一个插入索引

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

我稍微重写了你的函数。现在进行解释：

我假设 return 的索引是可以放置任何内容的第一个位置，这反过来会将所有后续项目移到右侧。

由于我们无法按设计合并列表范围之外的索引，因此我们必须检查元素是否大于列表末尾的项目。然后我们 return 下一个可能的索引 len(lis).

为了完全避免递归，我使用了 while 循环。首先，我们检查 left 是否等于或大于 right。这只有在我们找到放置元素的索引时才是正确的。

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

如果我们的元素大于 mid 处的项目，唯一可能的下一个选项是 select 下一个 未选中的位置 ，即 mid + 1.

现在进入有趣的部分。与另一种情况一样，要找到最左边的项目，我们必须将 right 边界设置为 mid - 1，以便跳过 mid 元素。但是，我们检查元素是否小于 或等于 mid 处的项目。这向我们保证，当我们找到等于搜索元素的候选者时，我们运行再次搜索（从右开始减少范围）以可能找到更小的索引。当 left == right 为真时，循环结束。

我希望这能回答您的问题并指出代码中的差异！

偏二分排序 Return 第一个插入索引

Biased Binary Sort Return First Index of Insertion

python

recursion

binary-search