O(log n)算法在排序数组中找到最佳插入位置 [英] O(log n) algorithm to find best insert position in sorted array

问题描述

我正在尝试寻找一种找到最佳位置的算法，以将 target 插入已排序的数组中.

I'm trying to make an algorithm that finds the best position to insert the target into the already sorted array.

目标是要么返回该项目在列表中的位置，要么返回将其保持排序的位置.

The goal is to either return the position of the item if it exists in the list, else return the position it would go into to keep the list sorted.

说我有一个清单:

   0   1   2   3   4    5    6
 ---------------------------------
 | 1 | 2 | 4 | 9 | 10 | 39 | 100 |
 ---------------------------------

我的目标商品是14 它应该返回5

And my target item is 14 It should return an index position of 5

我目前拥有的伪代码:

array = generateSomeArrayOfOrderedNumbers()

number findBestIndex(target, start, end)
    mid = abs(end - start) / 2

    if (mid < 2) 
        // Not really sure what to put here
        return start + 1 // ??

    if (target < array[mid])
        // The target belongs on the left side of our list //
        return findBestIndex(target, start, mid - 1)
    else
        // The target belongs on the right side of our list //
        return findBestIndex(target, mid + 1, end)

我不太确定现在要写些什么.我试图对此采取二进制搜索方法，但这是在5次重写左右之后我能想到的最好的方法.

I not really sure what to put at this point. I tried to take a binary search approach to this, but this is the best I could come up with after 5 rewrites or so.

推荐答案

您的代码有几个问题:

mid = abs(end - start) / 2

这不是 在start和end之间的中间，是它们之间距离的一半(向下舍入为整数).后来，您将其用作确实是有效的索引:

This is not the middle between start and end, it's half the distance between them (rounded down to an integer). Later you use it like it was indeed a valid index:

findBestIndex(target, start, mid - 1)

不是.您可能打算在此处使用mid = (start + end) // 2或其他名称. 您还会错过一些索引，因为您跳过了中途:

Which it is not. You probably meant to use mid = (start + end) // 2 or something here. You also miss a few indices because you skip over the mid:

return findBestIndex(target, start, mid - 1)
 ...
return findBestIndex(target, mid + 1, end)

您的基本情况现在也必须有所不同.一个好的人选就是条件

Your base case must now be expressed a bit differently as well. A good candidate is the condition

if start == end

因为现在您一定知道您已经完成搜索.请注意，还应考虑所有数组元素均小于target的情况，因此需要在末尾插入.

Because now you definitely know you're finished searching. Note that you also should consider the case where all the array elements are smaller than target, so you need to insert it at the end.

如果您从未做过二进制搜索，那么很难做到这一点.如果执行二进制搜索，通常会使用以下模式:

Binary search is something that is surprisingly hard to get right if you've never done it before. I usually use the following pattern if I do a binary search:

lo, hi = 0, n // [lo, hi] is the search range, but hi will never be inspected.
while lo < hi:
    mid = (lo + hi) // 2
    if check(mid): hi = mid
    else:          lo = mid + 1

在check是单调二进制谓词的条件下(直到某个点它始终是false，从该点开始一直是true)，在此循环之后，lo == hi将是范围[0..n]和check(lo) == true. check(n)被隐式地假定为真实(这是该方法不可思议的一部分).

Under the condition that check is a monotone binary predicate (it is always false up to some point and true from that point on), after this loop, lo == hi will be the first number in the range [0..n] with check(lo) == true. check(n) is implicitely assumed to be true (that's part of the magic of this approach).

那么对于包括我们目标位置和目标位置之后的所有索引而言，true是一个单调谓词是什么?对于之前的所有位置而言，false是一个单调谓词吗?

So what is a monotone predicate that is true for all indices including and after our target position and false for all positions before?

如果考虑到这一点，我们想在数组中找到比目标大的第一个数字，因此我们将其插入就可以了:

If we think about it, we want to find the first number in the array that is larger than our target, so we just plug that in and we're good to go:

lo, hi = 0, n
while lo < hi:
    mid = (lo + hi) // 2
    if (a[mid] > target): hi = mid
    else:                 lo = mid + 1
return lo;

这篇关于O(log n)算法在排序数组中找到最佳插入位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！