返回排序数组中每个数字的最后一个满足的函数 [英] function that returns the last met of each numbers in a sorted array

问题描述

我编写了一个函数，该函数返回从0到9的每个数字的第一个满足条件

I wrote a function that returns the first met of each numbers from 0 to 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.

result: 0 2 4 6 8 10 12 14 16 18 .

我试图编写一个函数，该函数返回从0到9的每个数字的最后一个满足条件.1 3 5 7 9 11 13 15 17 19

I tried to write a function that return the last met of each numbers from 0 to 9. and wanted to get: 1 3 5 7 9 11 13 15 17 19

但是它不能正常工作(你能帮我吗?这是我的功能.

But it does not works correctly( could you help me to with it? Here is my function.

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)

推荐答案

您需要返回 left-1 而不是 left .这是因为当您到达val mid 的最后一个索引时，第一个if将从 mid + 1 ( upper(a，val，mid + 1，右))

You need to return left-1 instead of left. This is because when you arrive at the last index of val mid, the first if will look from 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)

这篇关于返回排序数组中每个数字的最后一个满足的函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！