Найти ближайшее число в отсортированный список данной целевой количество


Дан список из N целых чисел, отсортированных в порядке возрастания, найти ближайший число (значение) в списке данной целевой номер. Как можно быстро вы сделать это?

Мне интересно знать, если есть какие-либо отзывы в моем коде.

def getClosestValue(arr, target):
    n = len(arr)
    left = 0
    right = n - 1
    mid = 0

    # edge case
    if (target >= arr[n - 1]):
        return arr[n - 1]
    # BSearch solution: Time & Space: Log(N) 

    while (left < right):
        mid = (left + right) // 2 # find the mid

        if (arr[mid] == target):
            return arr[mid]

        if (target < arr[mid]):
            # If target is greater than previous
            # to mid, return closest of two
            if (mid > 0 and target > arr[mid - 1]):
                return findClosest(arr[mid - 1], arr[mid], target)
            # update right
            right = mid
        else:
            if (mid < n - 1 and target < arr[mid + 1]):
                return findClosest(arr[mid], arr[mid + 1], target)
            # update i
            left = mid + 1
    return arr[mid]

# findClosest
# We find the closest by taking the difference
# between the target and both values. It assumes
# that val2 is greater than val1 and target lies
# between these two.

def findClosest(val1, val2, target):
    if (target - val1 >= val2 - target):
        return val2
    else:
        return val1


# Sample code
arr = [1, 2, 3, 4, 5, 5, 8, 10]
target = 7
print(getClosestValue(arr, target))


8143
5
задан 21 марта 2018 в 09:03 Источник Поделиться
Комментарии
2 ответа

Конвенций

Стиль руководства следовать в Python PEP8. Если вы сделаете это, ваш код сливается прямо в сообщество Python и сразу легче следовать. На этом плане вы увидите, что имя функции не соблюдать рекомендуемый стиль.

getClosestValue

На самом деле должны быть:

get_closest_value

Соответствующая цитата из PEP8 для этого случая


Использовать правила именования функции: строчные буквы С слова, разделенные
подчеркивает как необходимые для улучшения читабельности.

Еще в этой теме, все скобочки используются в ifs являются избыточными и нарушать стиль.

if (target >= arr[n - 1]):

Должны быть направлены на:

if target >= arr[n - 1]:

Хотя я подозреваю, что это может быть привычка, привезенная из других языков.

Крайние случаи

Вы рассматривали случай, когда значение является самым высоким или выше, который дает вам быстрый выход:

# edge case
if (target >= arr[n - 1]):
return arr[n - 1]

Однако нет соответствующего граничного случая, когда значение является минимальным или ниже. Я считаю, что вы просто забыли это.

#edge case - first or below all
if target <= arr[0]:
return arr[0]

Логика

Теперь обе крайние случаи покрываются, поэтому while можно упростить только навигация на соответствующий пункт, если он есть.

while (left < right):
mid = (left + right) // 2 # find the mid
if arr[mid] == target:
return arr[mid]

if target < arr[mid]:
right = mid
else:
left = mid + 1

После этого последнего while если нет точного совпадения, рассчитать ближайшего к одним вы закончили и вернуть его:

if target < arr[mid]:
return find_closest(arr[mid - 1], arr[mid], target)
else:
return find_closest(arr[mid], arr[mid + 1], target)

Обратите внимание, что я не нужно проверить, если mid - 1 или mid + 1 допустимый индекс, потому что если бы это не было это будет означать, что этот показатель был ниже или выше всех элементов, и эти случаи были уже охвачены в начале функции.
Это не только проще, но и эффективнее, поскольку он проверяет только на ближайший, на самом конце, а не на каждой итерации.

Принимая @bipll предложение можно перестроить while немного. Учитывая, что вы только получаете if arr[mid] == target на последней итерации вы можете сначала проверить < или >. Это дает возможность избежать дополнительной проверки, что не удастся в большинстве случаев:

while left < right:
mid = (left + right) // 2 # find the mid
if target < arr[mid]:
right = mid
elif target > arr[mid]:
left = mid + 1
else:
return arr[mid]


Когда у меня есть простое условие с return в обоих случаях я предпочитаю писать их встроенными, так ее легко читать и немного более кратким:

def find_closest(val1, val2, target):
return val2 if target - val1 >= val2 - target else val1

Но не пошел на это. Он легко может быть сложнее для чтения, в зависимости от сложности состояния.

Полную Модифицированную Версию

Для вас, чтобы получить лучшее представление о всех изменениях я уже говорил, я оставлю вам полную модифицированную версию:

def get_closest_value(arr, target):
n = len(arr)
left = 0
right = n - 1
mid = 0

# edge case - last or above all
if target >= arr[n - 1]:
return arr[n - 1]
# edge case - first or below all
if target <= arr[0]:
return arr[0]
# BSearch solution: Time & Space: Log(N)

while left < right:
mid = (left + right) // 2 # find the mid
if target < arr[mid]:
right = mid
elif target > arr[mid]:
left = mid + 1
else:
return arr[mid]

if target < arr[mid]:
return find_closest(arr[mid - 1], arr[mid], target)
else:
return find_closest(arr[mid], arr[mid + 1], target)

# findClosest
# We find the closest by taking the difference
# between the target and both values. It assumes
# that val2 is greater than val1 and target lies
# between these two.
def find_closest(val1, val2, target):
return val2 if target - val1 >= val2 - target else val1

3
ответ дан 22 марта 2018 в 01:03 Источник Поделиться

Python имеет двоичный поиск реализации: https://docs.python.org/2/library/bisect.html

так что просто:

import bisect
ind = bisect.bisect_left(arr, target)

если вы получаете Инд > лен(Арр)-2, то решение Арр[-1]. В противном случае вы просто hceck Арр[Инд] и arr[Инд+1], чтобы найти, в зависимости от близости

Строго говоря, если вы реализовали свой собственный бинарный поиск надо же, как быстро. Однако, имея две реализации строки легче читать, чем определение собственных функций

-2
ответ дан 22 марта 2018 в 08:03 Источник Поделиться