-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathfinal_search_in_broken_array.py
108 lines (90 loc) · 5.83 KB
/
final_search_in_broken_array.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
"""
A. Поиск в сломанном массиве
Алла ошиблась при копировании из одной структуры данных в другую. Она
хранила массив чисел в кольцевом буфере. Массив был отсортирован по
возрастанию, и в нём можно было найти элемент за логарифмическое время.
Алла скопировала данные из кольцевого буфера в обычный массив, но сдвинула
данные исходной отсортированной последовательности. Теперь массив не
является отсортированным. Тем не менее, нужно обеспечить возможность
находить в нем элемент за O(logn).
Можно предполагать, что в массиве только уникальные элементы.
Задачу необходимо сдавать с компилятором Make, он выбран по умолчанию,
других компиляторов в задаче нет. Решение отправляется файлом.
Требуемые сигнатуры функций лежат в заготовках кода на диске.
От вас требуется реализовать функцию, осуществляющую поиск в сломанном массиве.
Файлы с заготовками кода, содержащими сигнатуры функций и базовый тест для
поддерживаемых языков, находятся на Яндекс.Диске по ссылке. Обратите внимание,
что считывать данные и выводить ответ не требуется.
Расширение файла должно соответствовать языку, на котором вы пишете
(.cpp, .java, .go, .js, .py). Если вы пишете на Java, назовите файл с
решением Solution.java, для C# – Solution.cs. Для остальных языков
название может быть любым, кроме solution.ext, где ext – разрешение
для вашего языка.
Формат ввода
Функция принимает массив натуральных чисел и искомое число k.
Длина массива не превосходит 10000. Элементы массива и число k не превосходят
по значению 10000.
В примерах:
В первой строке записано число n –— длина массива.
Во второй строке записано положительное число k –— искомый элемент.
Далее в строку через пробел записано n натуральных чисел – элементы массива.
Формат вывода
Функция должна вернуть индекс элемента, равного k, если такой есть в массиве
(нумерация с нуля). Если элемент не найден, функция должна вернуть −1.
Изменять массив нельзя.
Для отсечения неэффективных решений ваша функция будет запускаться от 100000 до
1000000 раз.
Пример 1
Ввод
9
5
19 21 100 101 1 4 5 7 12
Вывод
6
"""
# {
# 'ID':'81024533',
# 'Вердикт': 'OK',
# 'Время':'0.718s',
# 'Память':'4.05Mb',
# }
def broken_search(nums: list, target: int) -> int:
"""
Функция принимает:
- nums (:obj:`list[int]`) список целых чисел
- target (:obj:`int`) и целое число
и возвращает индекс target в nums, если он присутствует и -1 в
противном случае.
В функции используется метод двоичного поиска с
измененным условием, учитывающим вращение входного списка. Цикл
while продолжается до тех пор, пока начальный индекс меньше или
равен конечному. На каждой итерации вычисляется средний индекс.
Затем проверяется, равен ли средний элемент целевому, если да,
то возвращается средний индекс. Если нет, то проверяется отсортирована
ли левая или правая часть массива и находится ли цель в этом диапазоне.
Если находится, то обновляется начальный или конечный индекс, иначе
обновляется другой. Если цикл завершается, а цель не найдена, функция
возвращает -1.
"""
start_index = 0
end_index = len(nums) - 1
while start_index <= end_index:
mid_index = start_index + ((end_index - start_index) >> 1)
if nums[mid_index] == target:
return mid_index
if nums[start_index] <= nums[mid_index]:
if nums[start_index] <= target < nums[mid_index]:
end_index = mid_index - 1
else:
start_index = mid_index + 1
else:
if nums[mid_index] < target <= nums[end_index]:
start_index = mid_index + 1
else:
end_index = mid_index - 1
return -1
def test():
arr = [19, 21, 100, 101, 1, 4, 5, 7, 12]
assert broken_search(arr, 5) == 6
if __name__ == '__main__':
test()