Last Updated: 11 Dec, 2020
Search an Element in an Array
Easy
Asked in companies
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
Approaches
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.
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 R<L then return false.
Else 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).
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.
Similar problems