Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Last Updated: 24 Feb, 2021

Sparse Search

Asked in companies

Problem statement

You are given a sorted array of strings say ‘ARR’ and provided with another string say ‘K’. Your task is to find the position of ‘K’ in ‘ARR’.

Note :
‘ARR’ can also contain empty strings.
You will return -1 if ‘K’ does not exist in ‘ARR’.
For example :
‘ARR’ = [ “code”, “hi”, “”, “”,  “studio”, “”, “to”, “welcome” ] and ‘K’ = “hi”.
 As we can see ‘K’ is present on index 1 in ‘ARR’.
 So we will return 1.
Input Format :
The first line of input contains a single integer T, representing the number of test cases.
Then the T test cases follow.

The first line of each test case contains an integer ‘N’ representing the size of ‘ARR’ and a string representing ‘K’.

The second line of each test case contains ‘N’ space-separated strings.

Output format :

For every test case, print a single integer representing the location of ‘K’ in ‘ARR’, if ‘K’ is not present in ‘ARR’ then print -1.

The output of each test case is printed in a separate line.
Note :
You don’t have to print anything. It has already been taken care of. Just implement the given function. 
Constraints :
1<= T <=100
1<= ‘N’ <=10^4
1<= |‘K’| <= 20

 Time limit: 1 second


01 Approach

The idea is very simple as we just need to find the position of ‘K’ in ‘ARR’. So we will scan ‘ARR’ from left to right and match each string with ‘K’, If we find a match simply return the index else keep on iterating till the end of ‘ARR’.


  • Iterate over ‘ARR’ for 0 <= i < ‘N’ and do :
    • If ‘ARR[i]’ is equal to ‘K’ return i.
  • Return -1 as we can not find ‘K’.