Searching a number

Problem

Given an array arr of n elements and a integer k. Your task is to return the position of first occurence of k in the given array and if element k is not present in the array then return -1 .

Note: Position of first element is considered as 1.

Examples:

Example 1:

Input:
n = 5
k = 16
arr = {9, 7, 2, 16, 4}
Output: 4
Explanation: k = 16 is found in the given array at position 4.

Example 2:

Input:
n = 7
k = 98
arr = {1, 22, 57, 47, 34, 18, 66}
Output: -1
Explanation: k = 98 isn't found in the given array.

Your task:

Complete the function search() which takes two integers n , k and an array arr, as input parameters and returns an integer denoting the answer. Return -1 if the number is not found in the array. You don't have to print answers or take inputs.

• Expected Time Complexity: $O(n)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1 <= n <= 10^6$
• $1 <= k <= 10^6$
• $1 <= arr[i] <= 10^9$

Solution

Python

def search(self, n : int, k : int, arr : List[int]) -> int:
    for i in range(0, n-1):
        if k==arr[i]:
            return i+1
    return -1

Java

public static int search(int n, int k, int[] arr) {
    for(int i = 0; i<n; i++) {
        if(k==arr[i])
            return i+1;
    }
    return -1;
}

C++

int search(int n, int k, vector<int> &arr) {
    for(int i = 0; i<n; i++) {
        if(k==arr[i])
            return i+1;
    }
    return -1;
}

C

int search(int n, int k, int arr[]) {
    for (int i = 0; i < n; i++) {
        if (k == arr[i])
            return i + 1;  
    }
    return -1;  
}

• Time Complexity: $O(n)$
• Auxiliary Space: $O(1)$