使用二分查找将元素插入已排序数组

Question

我想在已排序的数组中插入一个元素（替换现有元素）

[1, 2, 3, 4, 5]

例如，要插入0并保持顺序，应该将其替换为1。

[0, 2, 3, 4, 5]

为了插入6并保持顺序，应该用6替换5

[0, 2, 3, 4, 6]

我想使用二分查找，我创建了以下内容：

int binary_search(int *a, int first, int last, int x) {

    int mid;

    while (first <= last) { /* was <, changed to <= */

        mid = (first + last) / 2;

        if (a[mid] == x)
            return mid;

        else if (a[mid] > x)
            last =  mid - 1;

        else
            first = mid + 1;
    }

    /* after the loop => first = last */

    if (a[first] > x)
        return first;
    else
        return first + 1;
}

我是否漏掉了什么，如何证明我的所作所为能够产生始终正确的结果？

- user1781626

---

http://www.geeksforgeeks.org/search-floor-and-ceil-in-a-sorted-array/ 这是我问题的答案。 - user1781626

Answer 1

我通常做的，也是我认为证明算法正确性最简单的方法，就是将其视为最小单位。因此，让我们开始给出一个算法可能失败的场景，并测试它是否会失败。

假设first = 0，last=1。那么mid = (0+1)/2=0。所以有三种情况：

• 当a[mid] == x时，你找到了答案。
• 当a[mid] > x时，你将移动last = mid - 1 = -1，结束循环，因为last不大于first，而且因为x小于排序列表的第一个元素的值，所以x不可能在列表中。
• 当a[mid] < x时，你将移动first = mid + 1 = 1，现在这种情况下，你终止了循环。但是存在问题，因为a[1]可能包含你要查找的值。你只是跳过了一个可能的选择。

以下是算法失败情形的可视化演示。假设x = 5，并将F = first和L = last表示。

      (1   5)   6   7   8   9   15
       ^   ^ 
       F   L

如你所见，粗体部分是可能的选项。当first = 0且last = 1时，你有两个可能的选择，即a[0]和a[1]。然后，当你计算出mid = (0+1)/2=0，并且检测到a[mid] = a[0] = 1 < 5时，你将移动first = 1和last = 1。你终止循环，因为last不再大于first，在这种情况下，你只检查了a[0]，但跳过了a[1]。

---

所以我建议做以下事情：

def binarysearch(a, x):
    low  = 0
    high = length(a)

    while low <= high:
        mid = (high + low) / 2
        if     (a[mid] == x): return mid
        elseif (a[mid] > x) : low  = mid + 1
        else                : high = mid - 1

    return -1

在你的代码中，没有机制告诉你是否找不到正在搜索的项。当 x 没有找到时，我会返回 -1。因此，你可以简单地创建这样一个函数 replace。

def replace(a, x, y):
    # replace x with y 
    i = binarysearch(a, x)
    if i >= 0:
        a[i] = y
    else:
        print "x does not exist"

- invisal

---

谢谢，我现在已经将代码更改为first <= last。你的代码如果没有找到完全匹配项，则不会返回大于x的最小值。 - user1781626

我认为我在这里找到了答案，请查看http://www.geeksforgeeks.org/search-floor-and-ceil-in-a-sorted-array/。 - user1781626

Answer 2

我想对您的原始代码提出一些修改建议，这样您就可以确保您的代码始终给出正确的结果：

1. 在while循环中，您已经写成了while(first <= last)：应该将其更改为while(first < last)，因为在while循环之后，它将比较“x”与a[first]（或a[last]）。为了实现这一点，它们必须相同，即循环也必须在“first=last”的条件下中止。
2. 在while循环之后，我们需要添加一个检查，如果a[first]（或a[last]）等于x。如果是，则只需返回此索引的值。
3. 如果a[first] > x，则x可以插入到位置'first'。
4. 如果a[first] < x，则x将插入到位置'first+1'。

这是我的版本的代码：

int binary_search(vector<int> a, int first, int last, int x) {
    int mid;
    while (first < last) {
        mid = (first + last) / 2;
        if (a[mid] == x)
            return mid;
        else if (a[mid] > x)
            last =  mid - 1;
        else
            first = mid + 1;
    }
    if (start == a.size())
        return a.size();
    else if(a[first] > x)
        return first;
    else
        return first+1;
}

编辑：假设我们希望在{1,3,5,6}中插入7。为此，一旦我们退出循环，我们需要考虑“start”变量的最终值。如果它等于数组的大小，则新元素将放在末尾。我已相应地更新了代码。

- Abhinav

Answer 3

请注意您的代码。如果您想在0、2、3、4、5中用6替换5。 第一次迭代：first = 索引0，last = 索引4，mid = 索引2。3 < 6，所以现在first是索引3，last仍然是4。下一次迭代：first = 索引3，last = 索引4，mid = 索引3。4 < 6，所以现在first是索引4。4 !< 4，所以进入if，否则。a [4]是5，5 < 6，所以返回first + 1，即索引5。该索引现在已超出范围。

您需要确保不越界。另外，如果您有数字1 2 4 5，并且您想插入3。您会怎么做，覆盖2还是4？两者都可以。通过您的代码，您将自动替换4，但是您总是想替换更高的数字吗？也许您想选择最接近的数字？这只是一个需要考虑的问题。

- Ion