Поиск в сломанном массиве

Question

Выдает в двух тестах -1

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

def broken_search(nums, target) -> int:
    start = 0
    end = len(nums) - 1
    mid = end // 2
    if end == 0:
        if nums[0] == target:
            return 0
        return -1
    while start < end - 1:
        left = nums[start]
        middle = nums[mid]
        if target == middle:
            return mid
        elif target < middle:
            if left >= target:
                return binary_search(nums, target, start, mid)
            end = mid
            mid = (start + end + 1) // 2
        else:
            if target <= nums[end]:
                return binary_search(nums, target, mid, end)
            start = mid
            mid = (start + end + 1) // 2
    return -1

def binary_search(nums, target, start, end) -> int:
    if start >= end:
        if nums[end] == target:
            return start
        return -1
    mid = (start + end) // 2
    if target == nums[mid]:
        return mid
    elif target < nums[mid]:
        return binary_search(nums, target, start, mid - 1)
    else:
        return binary_search(nums, target, mid + 1, end)

if __name__ == '__main__':
    array = [19,21,100,101,1,4,5,7,12]
    print(broken_search(array, 50))

Answer 1

Решил не разбираться в вашем коде, но предоставить альтернативное решение. Сначала была идея воспользоваться бинарным поиском для нахождения сдвига. Но потом реализовал вот так:

def binary_search_for_broken(arr: list, search_value: int) -> int:
    start_value  = arr[0]
    start = 0
    end = len(arr) - 1
    while start <= end:
        middle = start + (end-start) // 2
        if search_value == arr[middle]:
            return middle
        if (arr[middle] < start_value) is not (search_value < start_value) or (arr[middle] > search_value):
            end = middle - 1
        else:
            start = middle + 1
    return -1

array = [19,21,100,101,1,4,5,7,12]
print(binary_search_for_broken(array, 1))
print(binary_search_for_broken(array, 50))
print(binary_search_for_broken(array, 12))
print(binary_search_for_broken(array, 101))

вывод соответственно

4
-1 # этого элемента в массиве не существует
8
3

БЛОГ НА HUSL

Поиск в сломанном массиве

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