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?

CodePudding user response：

Have you considered implementing some sort of binary search? Divide the array in half, if the value searched is greater than the the middle value take the second part and keep going. In pseudocode:

found = false
while(!found && array.length > 1){
   i = array.length / 2;
   if (array[i]==searchedValue) return true
   if (array[i]>searchedValue) array = array.slice(0, i)
   if (array[i]<searchedValie) array = array.slice(i 1, array.length)
}
if (array[0] == searchedValue) found = true
return found

This will decrease the complexity to O(log(n))

CodePudding user response：

You can use modified binary search that can find left most occurenct of the given target in the given array:

int binsearchLeftmost(int l, int r, int target, const std::vector<int>& array) {
    int res = 0;
    while (l <= r) {
        int m = l   (r - l) / 2;
        if (array[m] > target) {
            r = m - 1;
        }
        else if (array[m] < target) {
            l = m   1;
        }
        else {
            res = m   1;
            r = m - 1;
        }
    }
    return res;
}