Поиск в отсортированном массиве ⇐ Python

[Anonymous]

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

• N — это количество чисел, а k — количество выполняемых запросов.
• Следующая строка или строки содержат N чисел в неубывающем порядке. (данные) и k чисел (запросов) для поиска во входной последовательности.
• Числа разделяются пробелами и концами строк.

Считайте данные в память и для каждого запроса найдите первую позицию i в последовательности (т. е. наименьшее значение i, для которого data=х). Позиции индексируются от 1 до N.
Запишите все эти индексы в стандартный вывод в одну строку, разделенную пробелами. Если запрошенное число отсутствует в последовательности, вместо его позиции выведите 0. Если число присутствует более одного раза, выведите индекс его первого появления. Размер последовательности (N) и количество запросов (k) не превышают 1 000 000.

Код: Выделить всё

def custom_search(arr, target) -> int:
n = len(arr) + 1
for i in range(1, n):
if (arr[i-1] == target):
return(i)
return(0)

def give_numbers():
inputs = list(map(int, input().split()))
if len(inputs) != 2:
return([], None, None)
n, m = inputs
if ((n < 1 or n > 1000000) or (m < 1 or m > 1000000)):
return([], None, None)
i = 2
stuff = []
while i >= 1:
stuff.append(list(map(int, input().split())))
i -= 1
return(stuff, n, m)

inpt, n, m = give_numbers()
if len(inpt) != 0:
N, k = inpt
if n == len(N) and m == len(k):
for i in k:
print(custom_search(N, i), end=" ")

Inputs:
10 4
4 8 9 9 9 9 18 28 32 100
4 9 28 32

Outputs:
1 3 8 9

Есть ли лучший способ избежать O(n) при поиске в упорядоченном массиве и ускорить этот процесс?

Подробнее здесь: https://stackoverflow.com/questions/697 ... rted-array