Linear Search

Easy

0/40

Average time to solve is 10m

Contributed by

9 upvotes

Asked in company

Capegemini Consulting India Private Limited

Problem statement

You are given an array/list ‘ARR’ of ‘N’ positive integers’ and an integer ’X’. Your task is to find out the first instance of X in the array. If no such instance exists, return -1.

Note:

Consider 0-based indexing of the array.

For Example :

Input : arr[] = {5, 1, 3, 4, 3}, X = 3
Output : 2
There are two instances of 3 in the array -  2 and 4. Since we need to return the first instance our result is 2.

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

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases.Then ‘T’ test cases follow.

The first line of each test case contains the integer ‘N’ and ‘X’ representing the size of the input ‘ARR’ and the integer to be searched.

The next line of each test case contains ‘N’ single space-separated integers that represent the elements of the ‘ARR’.

Output Format :

For each test case, return the leftmost occurrence of integer X or -1.

Note:

You don’t need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 10^5
0 <= ARR[i] <= 10^9

Time Limit: 1 sec

Sample Input 1 :

2
6 1
2 6 2 8 4 5
1 1 
1

Sample Output 1 :

-1
 0

Explanation Of Sample Output 1 :

Since there is no instance of 1 in the input array we return -1.
In the second test case, the only occurrence of 1 is 0.

Sample Input 2 :

1
5 3
5 1 3 4 3

Sample Output 2 :

Hint 1

Traverse the array from left to right.

Approaches (1)

Approach 1

Linear Search

Approach:

We traverse the array from left to right.
If X is found at any index, say i, return i immediately.
If at the end of traversal no index i is found return -1.

Time Complexity

O(N), where ‘N’ is the size of ‘ARR’.

Since we traverse the array once and each comparison takes O(1) time we make O(N) comparisons in the worst case. Hence the time complexity is O(N).

Space Complexity

O(1)

Since only constant space is used for declaring loop variables.

(100% EXP penalty)

Linear Search

Console