Выдает в двух тестах -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))