Search an Element in an Array
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.

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

Question

Search an Element in an Array

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.

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

Accepted Answer

Step 1 : Pen and paper approach. Explain the problem statement first and then give them an algo.
Step 2 : He asked me to implement linear search
Step 3 : Asked about the time complexity of both linear and binary

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, a constant space is required.

Time Complexity: O(1)Explanation:

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).

Accepted Answer

Recursive binary search

We will use a recursive binary search to solve this problem. The idea of binary search is to discard half intervals by just one comparison.

Let's say A[mid] = middle element of the given array and X = any element to be searched. As the array is sorted so we can compare A[mid] with X. Then following three conditions can occur:

If A[mid] == X It means we have found X.
A[mid] < X It means all elements before A[mid] are also less than X as the array is sorted. So we can discard all elements before mid and search in the other half.

Consider the below example for a better understanding.

mid X

1 2 4 6 10

A[mid] = 4 and X = 6

As A[mid] < 6, so we can discard [1,2,4] and search X in [6,10].

3. A[mid] > X It means all elements after A[mid] are also bigger than X as the array is sorted. So we can discard all elements after mid and search in the other half.

Consider the below example for a better understanding.

X mid

1 2 4 6 10

A[mid] = 4 and X = 2

As A[mid] > 2, we can discard [4,6,10] and search X in [1,2]

So we will keep two pointers left and right, and based on a comparison of A[mid] and X, we will recur for either the left or right half.

Steps:

For each query, we do a binary search on an array A. If we found an element in the array, add 1 to the answer; otherwise, add 0 to the answer.

Function to check if element X is present in the array using recursive Binary Search.

bool binarySearch(A,X,L,R):

If RElse Calculate mid, mid = L + (R - L) / 2;.
then If X == A[mid] return true.
then If X < A[mid], then search X in the left half of the array using recursion i.e. recur for left half and make R = mid – 1 i.e we call binarySearch(A,X,L,mid-1).
then If X > A[mid] then search X in the right half of the array using recursion i.e. recur for right half and make L= mid+1. i.e we call binarySearch(A,X,mid+1,R,X).

Space Complexity: O(1)Explanation:

O(logN), where ‘N’ denotes the total number of elements in the array.

In the worst case, when an element is not present in the array, we will need log(N) recursion calls. Hence the overall complexity will be O(logN).

Time Complexity: O(1)Explanation:

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

Proof :

Let's say the initial length of our array = N. At each iteration, the length of the array is reduced by half. So we will Get Recurrence as T(N) = T(N/2) + C, Here C is some constant.

After 1st iteration length of array = N/2

After 2nd iteration length of array = N/4

After 3rd iteration length of array = N/8

.

After kth iteration length of array = N/(2^k)

Also, We know that the length of the array will become 1 after k iterations. So N/(2^k) = 1

2^k = N

Taking log base 2 both sides

Log(2^k) = Log(N)

We know that log(2^k) = k

K = logN

So time complexity for the Q query is logN.

For Q queries, it will be Q*logN.

Hence the overall time complexity will be O(Q*logN).

Accepted Answer

Iterative binary search

Instead of recursive binary search, we will use iterative binary search to check if the element in the array is present or not.

Steps:

For each query, we do a binary search on an array A. If we found an element in the array, add 1 to the answer; otherwise, add 0 to the answer.

Function to check if element X is present in the array using iterative Binary Search.

bool binarySearch(A,N,X):

Initialize left = 0 and right = N-1
Calculate mid, mid = left + (right - left) / 2.
then If X == A[mid] return true.
then If X < A[mid], search X in left half of array by doing right = mid - 1
then If X > A[mid] ,search X in right half by doing left = mid+1.
Repeat step 2 to 5 until left <= right.
At last, return false.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, a constant space is required.

Time Complexity: O(1)Explanation:

O(Q*logN) 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)), we do a binary search which takes O(logN) time to search elements in the array. Hence the overall time complexity will be O(Q*logN).

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 :

Input format:

Output Format:

Note:

Constraints:

Top TCS Associate Software Engineer interview questions & answers

Popular interview questions of Associate Software Engineer

Top HR questions asked in TCS Associate Software Engineer