O(log n)算法在排序数组中找到最佳插入位置

Question

我正在尝试制作一个算法,找到将目标插入已排序数组的最佳位置.

目标是返回项目的位置(如果它存在于列表中),否则返回它将保持列表排序的位置.

所以说我有一个清单:

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

而我的目标项是14 它应该返回索引位置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次重写后可以想出的最好的方法.

Answer 1

你的代码有几个问题:

mid = abs(end - start) / 2

这是不是之间的中间start和end,这是他们之间的距离的一半(四舍五入到整数).后来你使用它就像它确实是一个有效的索引:

findBestIndex(target, start, mid - 1)

它不是.你可能想在mid = (start + end) // 2这里使用或者其他东西.你也错过了几个指数,因为你跳过了中期:

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

现在,您的基本情况也必须表达不同.一个好的候选人是条件

if start == end

因为现在你肯定知道你已经完成了搜索.请注意,您还应该考虑所有数组元素都小于的情况target,因此您需要在最后插入它.

我不经常搜索二进制文件,但如果我这样做,就是这样

如果你以前从未做过二进制搜索,那么令人惊讶地难以找到它.如果我进行二分查找,我通常使用以下模式:

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)隐含地假设是真的(这是这种方法的魔力的一部分).

那么true所有指数的单调谓词是什么,包括在我们的目标位置之后以及false之前的所有位置？

如果我们考虑一下,我们想要找到数组中第一个大于目标的数字,所以我们只需插入它就可以了:我们很高兴:

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