美文网首页
getFirstk和getLastk

getFirstk和getLastk

作者: Haward_ | 来源:发表于2019-04-23 12:07 被阅读0次
def getFirstk(arr,k):
    if len(arr) == 0 or arr[0] > k or arr[-1] < k:
        return -1

    i,j = 0,len(arr)-1
    while i <= j:
        m = i + int((j-i)/2)
        if arr[m] < k:
            i = m + 1
        else:
            j = m
        if i == j:
            return i if arr[i] == k else -1
    return -1

def getLastk(arr,k):
    if len(arr) == 0 or arr[0] > k or arr[-1] < k:
        return -1

    i,j = 0,len(arr)-1
    while i <= j:
        m = i + int((j-i)/2)
        if arr[m] > k:
            j = m - 1
        else:
            i = m
        if i == j:
            return i if arr[i] == k else -1
    return -1

if __name__ == "__main__":
    arr = [1,2,2,2,4,5]
    k = 2
    res = getLastk(arr,k)
    print(res)

相关文章

网友评论

      本文标题:getFirstk和getLastk

      本文链接:https://www.haomeiwen.com/subject/ylqvgqtx.html