Поиск в сломанном массиве (ошибка в тестах, нужна помощь найти ошибку)

Question

Задача: Алла ошиблась при копировании из одной структуры данных в другую. Она хранила массив чисел в кольцевом буфере. Массив был отсортирован по возрастанию, и в нём можно было найти элемент за логарифмическое время. Алла скопировала данные из кольцевого буфера в обычный массив, но сдвинула данные исходной отсортированной последовательности. Теперь массив не является отсортированным. Тем не менее, нужно обеспечить возможность находить в нем элемент за O(logn). Можно предполагать, что в массиве только уникальные элементы.

Решение:

def binary_search(array, target, left, right):
    mid = (left + right) // 2
    if array[mid] == target:
        return mid
    if left == right:
        return -1
    # # left normal part
    if array[0] < array[mid]:
        if target >= array[0]:
            if target > array[mid]:
                return binary_search(array, target, mid + 1, right)
            return binary_search(array, target, left, mid)
        return binary_search(array, target, mid + 1, right)
    # left broken part
    if target < array[0]:
        if target < array[mid]:
            return binary_search(array, target, left, mid)
        return binary_search(array, target, mid + 1, left)
    return binary_search(array, target, left, mid)


def broken_search(array, target):
    return binary_search(array, target, 0, len(array) - 1)

В тестах со входным списком 5, 1 ответ выдает -1, вместо 1. (то есть индекс числа 1 в данном примере = 1, хотя и -1 тоже правильно, как последний элемент, но нужно удовлетворить тесты). Где найти ошибку?

Answer 1

Если mid подвинуть правее, чтобы алгоритм не клинило на списке из двух элементов, то всё работает. Проверено на всех перестановках списков длин до 1000 элементов.

def binary_search(array, target, left=0, right=None):
    if right is None: right = len(array)-1
    if not array: return -1
    mid = (left + right + 1) // 2
    if array[mid] == target:
        return mid
    if left == right:
        return -1
    # left normal part
    if array[0] < array[mid]:
        if target >= array[0]:
            if target > array[mid]:
                return binary_search(array, target, mid, right)
            return binary_search(array, target, left, mid-1)
        return binary_search(array, target, mid, right)
    # left broken part
    if target < array[0]:
        if target < array[mid]:
            return binary_search(array, target, left, mid-1)
        return binary_search(array, target, mid, right)
    return binary_search(array, target, left, mid-1)

# tests
for i in range(1000):
    seq = list(range(i))
    
    # positive tests
    for p in range(i):
        r = binary_search(seq, 0)
        #print(seq, "=>", r)
        assert r == p, f"Tests FAILED! Expected {p}, got {r} for {seq}"
        seq = [seq.pop()] + seq

    # negative tests
    r = binary_search(seq, -1)
    assert r == -1, f"Tests FAILED! Expected -1, got {r} for {seq}"
    r = binary_search(seq, i)
    assert r == -1, f"Tests FAILED! Expected -1, got {r} for {seq}"

    if seq:
        m = len(seq) // 2
        seq.pop(m)
        for p in range(i-1):
            r = binary_search(seq, m)
            assert r == -1, f"Tests FAILED! Expected -1, got {r} for {seq}"
            seq = [seq.pop()] + seq

print("Tests PASSED")

БЛОГ НА HUSL

Поиск в сломанном массиве (ошибка в тестах, нужна помощь найти ошибку)

Ответы (1 шт):