returns 排序数组中每个数字的最后一次相遇的函数

Question

我写了一个函数，return是从 0 到 9 的每个数字的第一个集合

array = [0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9]


def lower(a, val, left, right):
    if left == right:
        return left
    mid = (left + right) // 2

    if a[mid] < val:
        return lower(a, val, mid+1, right)
    else:
        return lower(a, val, left, mid)

for i in range(10):
    print(lower_bound(array, i , 0, len(array)-1), end =' ')

结果：0 2 4 6 8 10 12 14 16 18 .

我尝试编写一个函数，return 每个数字从 0 到 9 的最后一次相遇。并希望获得： 1 3 5 7 9 11 13 15 17 19

但它不能正常工作( 你能帮我解决吗？这是我的功能。

def upper(a, val, left, right):

    if left == right:
        return left
    mid = (left + right) // 2

    if a[mid] <= val:
        return upper(a, val, mid+1, right)
    else:
        return upper(a, val, left, mid)

Answer 1

原因是，在每一种情况下，您都在最后一次出现并且 right 是之后的一个索引，您找到了合适的索引，但继续向前移动了一步。该算法似乎不错，但只需消除这种情况，一切正常：

array = [0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9]

def upper(a, val, left, right):

    if left == right:
        if a[left] == val:
            return left
        else:
            return left-1
    mid = (left + right) // 2
    if a[mid] <= val:
        return upper(a, val, mid+1, right)
    else:
        return upper(a, val, left, mid)
        

for i in range(10):
    a = upper(array,i,0,19)
    print(a)

输出：

为其他几个人检查过它，我认为它工作正常

Answer 2

您需要 return left-1 而不是 left。这是因为当你到达 val mid 的最后一个索引时，第一个 if 将从 mid+1 (upper(a, val, mid+1, right))

开始查找

def upper(a, val, left, right):

    if left == right:
        return left-1
    mid = (left + right) // 2

    if a[mid] <= val:
        return upper(a, val, mid+1, right)
    else:
        return upper(a, val, left, mid)

Answer 3

计算时使用floor函数mid表示函数不对称。你不能只反映其中的一部分而不考虑另一部分。

def upper(a, val, left, right):
    if left == right:
        return left
    mid = (left + right + 1) // 2

    if a[mid] > val:
        return upper(a, val, left, mid-1)
    else:
        return upper(a, val, mid, right)

Answer 4

寻找第一次见面：

for i in range(10):
  print(array.index(i))

查找最后一次见面：

inverted_array = array[::-1]
for i in range(10):
  print(len(array) - 1 - inverted_array.index(i))

returns 排序数组中每个数字的最后一次相遇的函数

function that returns the last met of each numbers in a sorted array

python

algorithm

binary-search