0

Задача: найти k чисел, ближайших к заданному значению, в упорядоченном массиве. Само значение может не встретиться в массиве. Пример:

closest([1,4,8,10], target=2, count=3) --> [1, 4, 8]

Решение должно иметь сложность O(log(n)+k). Использовать модуль bisect запрещено.

1
  • 3
    Ну и в чем ваша проблема? Что вы пытались, что не получилось?
    – EzikBro
    13 ноя 2021 в 16:03

2 ответа 2

3

Пишете сами бинарный поиск для определения позиции элемента, потом идёте от неё вправо и влево (если разница с левым элементом меньше, то уменьшаете левый индекс, иначе увеличиваете правый), пока не наберёте k чисел.

def BS(arr, value):
    lo = 0
    hi = len(arr)-1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == value:
            return mid
        elif arr[mid] < value:
            lo = mid + 1
        else:
            hi = mid - 1
    return -lo

a = [1,4,8,10]
value = 2 # 4, 8, -1, 15
k = 3
p = BS(a, value)
if p >= 0:
    l = p - 1
    r = p + 1
    n = 1
else:
    l = -p - 1
    r = -p
    n = 0

while n < k and l >= 0 and r < len(a):
    if value - a[l] <= a[r] - value:
        l -= 1
        n += 1
    else:
        r += 1
        n += 1
while n < k and l >= 0:
    l -= 1
    n += 1
while n < k and r < len(a):
    r += 1
    n += 1


if k==n:
    print(a[l+1:r])
3
  • бинарный поиск написал, а что делать если элемента нет в списке или разница равна?
    – lian
    13 ноя 2021 в 16:10
  • Обычно возвращают -1, если элемент не найден, а вы в этом случае возвращайте позицию, в которую был бы вставлен искомый элемент (left или lo обычно называют эту переменную)
    – MBo
    13 ноя 2021 в 16:14
  • И да, ещё нужен признак, что элемент есть в массиве
    – MBo
    13 ноя 2021 в 16:21
0
def binarySearch(data, val):
    highIndex = len(data)-1
    lowIndex = 0
    while highIndex > lowIndex:
            index = (highIndex + lowIndex) // 2
            sub = data[index]
            if data[lowIndex] == val:
                return [lowIndex, lowIndex]
            elif sub == val:
                return [index, index]
            elif data[highIndex] == val:
                return [highIndex, highIndex]
            elif sub > val:
                if highIndex == index:
                        return sorted([highIndex, lowIndex])
                highIndex = index
            else:
                if lowIndex == index:
                        return sorted([highIndex, lowIndex])
                lowIndex = index
    return sorted([highIndex, lowIndex])

def closest(array: list, target: int, count: int) -> list:

    index = binarySearch(array, target)[1]
    res = []

    if index == len(array) - 1:
        res += array[0-count:len(array)+1]
        return sorted(res)

    res.append(array[index]) if array[index] == target else array.insert(index, target)

    l, r, = 1, 1
    while len(res) != count:
        if abs(array[index] - array[index - l]) <= abs(array[index] - array[index + r]):
            res.append(array[index - l])
            l += 1
        else:
            res.append(array[index + r])
            r += 1

    return sorted(res)

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.