Search in sorted array

There is quite simple task for finding values in sorted array which may contain duplicities and return indices to standard output on a single line.

First line of the input contains the numbers N and k, separated by a space.

• N is the count of numbers and k is the number of queries to perform.
• The next line or lines contain N numbers in non-decreasing order (data) and k numbers (queries) to search for in the input sequence.
• Numbers are separated by spaces and ends of lines.

Read the data into memory and for each request find its first position i in the sequence (i.e., the smallest value i for which data[i]=x). Positions are indexed from 1 to N.

Write all these indices to standard output on a single line, separated by spaces. If the requested number is not present in the sequence, output 0 instead of its position. If the number is present more than once, output the index of its first occurence. The size of the sequence (N) and number of the requests (k) are at most 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

Is there any better way to avoid O(n) in searching in ordered array and speed this up?

The algorithm you are looking for is called binary search, and its time complexity is O(log2(N)).
Here is a python function that has 2 parameters:

1. The value you are looking for
2. The sorted array

and it returns the first position i where array[i] = value

def find_first_appearence(value, array):
    position = 0
    left = 0;
    right = len(array) - 1
    while left <= right:
        middle = int(left + (right - left) / 2)
        if array[middle] >= value:
            right = middle - 1
            position = middle
        else:
            left = middle + 1
    if array[position] != value:
        return 0
    return position