python - 对第一个平方大于或等于 k ​​的元素进行二分查找

Question

我正在编写一段代码来查找排序列表中第一个元素的索引，其平方大于或等于某个 k。我使用普通的二进制搜索作为框架并对其进行了修改以满足我的需要。我的想法是，平方大于或等于某个 k 的第一个元素本身应该大于或等于 k，并且其左侧的元素（列表已排序）的平方应该小于 k。我考虑了这些条件，当正确答案是索引 1（列表中的“4”）时，程序只返回正确答案，并且它立即返回 -1 和大多数另一个 k。我尝试调试它但没有成功，请帮助我！谢谢你！

def Bsearch(a, k):
    high = len(a) - 1
    low = 0
    while high > low:
        mid = (high - low) // 2
        num = a[mid] * a[mid]
        left = a[mid - 1] * a[mid - 1]
        if num >= k and left < k:
            return mid
        elif left >= k:
            return Bsearch(a[:mid], k)
        elif num < k:
            return Bsearch(a[mid + 1:], k)
    return -1

a = [1, 4, 5, 6, 7, 8, 19, 20]
k = 45
print(Bsearch(a, k))

标签： pythonbinary-search