Problem

Submissions

Hints & solutions

Discuss

Search an Element in an Array

Easy

0/40

Average time to solve is 15m

Contributed by

28 upvotes

Asked in companies

Problem statement

You have given a sorted array 'A' of 'N' integers.

Now, you are given 'Q' queries, and each query consists of a single integer 'X'. Your task is to check whether 'X' is present in array 'A' or not for each query. If 'X' exists in array 'A', you need to print 1 else print 0.

Note :

The given array is sorted in non-decreasing order.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of the input contains an integer 'T' representing the number of test cases or queries to be processed. Then the 'T' test case follows. 

The first line of each test case contains a single integer 'N' denoting the size of the array 'A'.

The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'A'.

The third line of each test contains a single integer 'Q', denoting the number of queries. 

Then each of the 'Q' lines from the fourth line of each test case contains a single integer 'X', denoting the desired element to be searched.

Output Format:

For each test case, print 'Q' space-separated integers that denote the answer to the given 'Q' queries, i.e., print 1 if the desired value 'X' exists in the array 'A', otherwise print 0.

Print the answer for each test case in a new line.

Note:

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10 
1 <= N <= 10^5    
-10^9 <= A[i] <= 10^9 
1 <= Q <= 10^4
-10^9 <= X <= 10^9

Where 'T' represents the number of test cases, 'N' represents the size of the array, 'A[i]' represents the elements of the array, 'Q' represents the number of queries and, 'X' denotes the number to be searched.
Time limit: 1 sec

Sample Input 1:

Sample Output 1:

1 0

Explanation for sample input 1:

For the first test case, the given array A is [1, 3, 5, 7,8].

So the answer for the given first query is 1 as 5 is present in the array.

For the second query answer is 0 as 2 is not present in the array.

Sample Input 2:

1
6
1 2 2 3 4 10
3
5
7 
2

Sample Output 2:

 0 0 1

Explanation for sample input 2:

For the first test case, the given array A is [1, 2, 2, 3, 4, 10].

So the answer for the given first query is 0 as 5 is not present in the array.

For the given second query answer is 0 as 7 is not present in the array.  

For the given third query answer is 1 as 2 is present in the array.

Hint 1

Hint 2

Hint 3

Think of a brute force solution.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

The idea here is to do a linear search which apparently is a brute force way, so for each query:

Visit every element one by one.
Check if the current element is equal to X or not. If yes, then we will add 1 to the answer.
Once all the elements are visited, and we don't find the X value, then add 0 to the answer.

Time Complexity

O(Q*N) per test case, where ‘N’ is the size of the given array, and ‘Q’ is the number of queries given.

In the worst case, for each query (O(Q)), when element ‘X’ is not present in the array, we need to traverse the whole array, which takes O(N) time. Hence the overall time complexity will be O(Q*N).

Space Complexity

O(1).

In the worst case, a constant space is required.

(100% EXP penalty)

Search an Element in an Array

Console