如果找不到值，则在二进制搜索中返回较小的数字

Question

我有一个排序数字列表。 [1,2,4,6,10,12]

我想在列表中查找号码。如果我找不到它，我想 return 下一个最小的数字。

例如，n = 8。我搜索 8 但找不到。然后我会 return 6 因为它是下一个最小的数字。

我有一些代码，但我似乎无法获得正确的索引：

def search_val(data, n):
    low = 0
    high = len(data) - 1
    if data[-1] <= n:
        return data[-1]
    if data[0] >= time:
        return

    while low < high:
        mid = (low + high) / 2
        if data[mid] == n:
            return data[n]
        if data[mid] > n:
            high = mid -1
        if data[mid] < n:
            low = mid + 1
    if data[low] < n:
        return data[low]
    else:
        return data[low - 1]

Answer 1

这将解决您所有的问题，而且应该会更快一些：

def search_val(data, n):
    low = 0
    high = len(data) - 1

    while low <= high:
        mid = (low + high) // 2

        if data[mid] > n:
            high = mid -1
        elif data[mid] < n:
            low = mid + 1
        else:
            return data[mid]

    # Now low > high

    if high >= 0:
        return data[high]

    # All values are > n.  Just return the first.  Could
    # be changed to return None.

    return data[0]

请注意，在所有值为 > n 的情况下，它 return 是第一个值。如果需要，您当然可以将其更改为 return None。

另请注意，它假定 len(data) 为 >= 1。如果情况并非总是如此，您可以在顶部添加一个检查，如果 data 是空列表，则 return None。

Answer 2

列表保证是有序的吗？如果没有，试试这个：

data = [1,2,4,6,10,12]
result = max((n for n in data if n <= 8))

如果找不到值，则在二进制搜索中返回较小的数字

returning lower number in binary search if value cannot be found

python

binary-search