Поиск ближайшего числа, равного или большего заданного числа

#python #function

#python #функция

Вопрос:

У меня есть функция Python, в которой мне нужно найти число в списке «значения», которое ближе всего к заданному числу «n», но больше или равно «n».

Пока у меня есть это:

 def nearest_largest_value2 (n, values):
      closest = []
      for i in values:
        if i == n:
          closest = i
        elif (i > n) and (i-n < 2):
          closest = i
       return closest

print(nearest_largest_value2(5, [1,3,4,6,7]))
print(nearest_largest_value2(5, [7,6,4,3,1]))
print(nearest_largest_value2(5, [1,3,4,5,6,7]))

Проблема в том, что я получаю ответ, который я хочу для первых двух операторов печати (6)
но я получаю ‘6’ для последнего оператора печати, когда я хочу получить 5.

Я новичок в Python, но я думал, что как только первое if предложение будет выполнено, код остановится.

Ответ №1:

Условие i-n < 2 неверно. Вместо этого вы должны проверять, i ближе ли текущее значение, чем текущее closest . Например.:

 def nearest_largest_value2 (n, values):
  closest = None
  for i in values:
    if (i >= n) and (closest is None or i < closest):
      closest = i
  return closest

Редактировать:

Альтернативный способ описать проблему — найти минимальное значение, которое больше или равно n . Подобное описание проблемы позволяет использовать более «питоновскую» линейку:

 def nearest_largest_value2 (n, values):
    return min(v for v in values if v >= n)

ПРАВКА2:

Как указал @ekhumoro, альтернативное решение, представленное в предыдущей правке, сломается, если values не содержит какого-либо элемента, равного или большего, чем n . Он также любезно предложил исправить это:

 def nearest_largest_value2 (n, values):
    min([v for v in values if v >= n] or [None])

1. @PranavHosangadi values[0] не обязательно равно или больше n . Здесь вы могли бы провести оптимизацию, при которой вы повторяете список до первого приемлемого элемента, не проверяя, является ли он ближайшим, а затем в другом цикле, который проверяет, находится ли элемент ближе

2. Почему бы просто не i < closest ? Кроме того, альтернативное решение не будет работать, если каждое значение меньше n .

3. @ekhumoro Хорошая точка зрения i<closest . Попал в оригинальную реализацию OP, где я не должен был. Отредактировано и улучшено, спасибо!

4. @Mureinik Одним из способов исправить альтернативное решение было бы: min((v for v in values if v >= n] or [None]) . Не очень красиво, но, по крайней мере, это дает эквивалентный результат.

Ответ №2:

Если у вас есть несколько запросов с разными номерами, но к одному и тому же списку, то более эффективно сначала отсортировать список, а затем выполнить по нему двоичный поиск.

 from bisect import bisect_left

values = [7, 6, 4, 3, 1]

values.sort()

def nearest_largest_value2 (n, values):
    try:
        result = values [bisect_left (values, n)]
    except IndexError: # when number is > every element of list 
        result = None
    return result

print (nearest_largest_value2 (5, values)) # 6
print (nearest_largest_value2 (3, values)) # 3
print (nearest_largest_value2 (8, values)) # None

Пусть p соответствует length of 'values' list и q соответствует number of inputs 'n' (или вызывается # times nearest_largest_value2 ).

В указанном случае временная сложность предыдущего решения O(pq) тогда как временная сложность текущего решения O((p q)logp) .