使用divide and conquer返回元素索引

Question

所以我们有一个未排序的数组，其中每个元素是下一个元素的±1 (|Ai-Ai+1|<=1)。给定一个元素k，如果找到，则返回数组A中k的索引。

这是我想出来的：

 def find(x,k,z):
    if(len(x) == 1 and x[0] != k):
        return -1
    mid = len(x)//2
    if x[mid] == k:
        return mid + z
    elif abs(x[mid] - k) <= 1:
        return find(x[:mid],k,mid+z)
    else:
        return find(x[mid:],k,mid+z)

这是我使用的x=1，2，3，4，5，4，3，3，2，3，4，5，6，7，8的数组；代码似乎对除6和2之外的每个元素都有效，其中它返回-1。

Answer 1

检查代码中的off-by-one错误。因此，一定要理解Python列表切片是如何工作的。例如,

a = [0, 1, 2, 3, 4, 5]
print(a[:2])
# [0, 1]
print(a[2:])
# [2, 3, 4, 5]

这意味着当您执行x[:mid]时，您从列表的末尾排除了mid元素。但是你从一开始就包含了x[mid:]元素。

这就是你想做的吗？

另外，您可能会发现，将左、右索引带入递归调用比将左偏移量作为z更容易理解(也更有效)。使用left，right有助于避免切片和偏移算法中的一堆边缘问题。

Answer 2

看起来像是intermediate value theorem的离散同类的用例。

一种几乎依附于所建立的最后一点信息的实现：

def _index_of(values, key, lo, dlo, hi, dhi):
    """ Return index of one occurrence of key in values from lo to hi. 
        Needs abs(values[i] - values[i+1]) <= 1, dlo/dhi == values[lo/hi] and
        (values[lo] < key < values[hi] or values[hi] < key < values[lo]). """
    while True:
        mid = lo + (hi - lo) // 2
        if mid <= lo:
            return -1
        value = values[mid]
        d = value - key
        # print(lo, dlo, mid, d, hi, dhi)
        if d * dlo <= 0:  # key should occur in values[lo:mid+1]
            if d == 0:
                return mid
            hi = mid
            dhi = d
        else:
            lo = mid + 1  # mid + abs(d) would be the only place sign mattered
            dlo = values[lo] - key
            if dlo == 0:
                return lo

def index_of(values, key, z=0):
    """ Return index of one occurrence of key in values, -1 if none. """
    # if values is None:
    #   return -1
    last = len(values) - 1
    if last < z:
        return -1
    dz = values[z] - key
    dl = values[last] - key
    if 0 <= dz * dl:
        if 0 == dz:
            return z
        if 0 == dl:
            return last
        raise "can't guarantee fast result"
    return _index_of(values, key, z, dz, last, dl)


if __name__ == '__main__':
    x = [1,2,3,4,5,4,3,3,2,3,4,5,6,7,8]
    def t(x):
        for v in set(x):
            print(v, index_of(x, v))
    t(x)

Answer 3

这里有一种方法，你可以通过寻找理论上的最大值和最小值来确定一个子列表是否能够保存搜索值。这样，你就可以修剪一些树枝了。

你的方法和这个之间的区别:在这里，我们看两个部分。而且还短路了不可能的分支仍然尝试实现O(log )

from math import ceil
from typing import List

def th_min_max(x: List[int], li: int, ri: int) -> int:
    """
    Find the theoretical maximum and minimum values
    for all elements between two known "anchor" values
    x is the data, where each abs(x[i] - x[i+1] <= 1)
    li, ri are the indexes of the anchors.
    """
    assert li <= ri
    # these are known values at the anchor locations.
    v1 = x[li]
    v2 = x[ri]
    # so how high/low can the numbers inbetween go?
    # the theoretical maximum is a sustained increase followed by a sustained decrease.
    num_changes = ri - li
    # some of the numbers are used to bridge difference between v1, v2
    remaining = num_changes - abs(v1 - v2)
    assert remaining >= 0, f"The input array does not meet constraints; look at [{li}] --> {v1} and [{ri}] --> {v2}"
    # so now we are look at maximum increase/decrease possible once we've bridged
    # the gap between the two known numbers.
    # half the remaining changes have to be used to 'undo' the initial changes
    # if there is an odd number, the remaining one can be max/min,
    # so use the ceil( ) function to round up.
    biggest_delta = int(ceil(remaining / 2))
    return (min(v1, v2) - biggest_delta, max(v1, v2) + biggest_delta)

有了最小/最大函数，我们可以进行分区算法：

def find(x: List[int], li: int, ri: int, search: int) -> int:
    """
    finds _some_ index where the search value is found in x 
    between index li and index ri; -1 if not found.
    """
    # first, if li = ri, this is a trivial is this it? question
    if li == ri:
        return li if x[li] == search else -1
    # second, figure out if this range could possibly have the number
    mn, mx = th_min_max(x, li, ri)
    if search < mn:
        # value being looked for _cannot_ be in range [li, ri]
        return -1
    if search > mx:
        # value being looked for _cannot_ be in range [li, ri]
        return -1
    mid = int((li + ri)/2)
    # we ma have to look both ways, but let's start on the
    # side with the anchor value closer to search value
    if abs(x[li] - search) <= abs(search - x[ri]):
        # go left first, then right.
        first = find(x, li, mid, search)
        return first if first >= 0 else find(x, mid + 1, ri, search)
    else:
        # go right first, then left
        first = find(x, mid + 1, ri, search)
        return first if first >= 0 else find(x, li, mid, search)

测试您的输入：

d = [1,2,3,4,5,4,3,3,2,3,4,5,6,7,8]

for search in d:
    res = find(d, 0, len(d)-1, search)
    print(search, res, d[res])

-->

1 0 1
2 1 2
3 6 3
4 5 4
5 11 5
4 5 4
3 6 3
3 6 3
2 1 2
3 6 3
4 5 4
5 11 5
6 12 6
7 13 7
8 14 8