New update is available. Click here to update.

Last Updated: 24 Feb, 2021

Difficulty: Easy

```
‘ARR’ can also contain empty strings.
You will return -1 if ‘K’ does not exist in ‘ARR’.
```

```
‘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.
```

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

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

```
You don’t have to print anything. It has already been taken care of. Just implement the given function.
```

```
1<= T <=100
1<= ‘N’ <=10^4
1<= |‘K’| <= 20
Time limit: 1 second
```

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

The idea is to binary search on ‘ARR’ as ‘ARR’ is sorted. However, it would have been much easier to implement a binary search if we were not given empty strings in ‘ARR’. But still, we can use the binary search with some modification. So on encountering an empty string while performing binary search we will simply move to the closest non-empty string.

- Initialize two integer variables ‘START’ = 0 and ‘END’ = ‘N’ - 1.
- Keep on iterating while ‘START’ <= ‘END’ and do:
- Initialize an integer variable ‘MID’ = (‘START’ + ’END’) / 2.
- If ‘ARR[MID]’ is an empty string then do:
- Find the closest non-empty string :
- Let’s ‘LEFT’ = ‘MID’ - 1 and ‘RIGHT’ = ‘MID’ + 1.
- Iterate while ‘LEFT’ >= ‘START’ or ‘RIGHT’ <= ‘END’ and do:
- Check if ‘ARR’ on the ‘LEFT’ index or ‘RIGHT’ index has a non-empty string and assign that index to ‘MID’.
- Decrease ‘LEFT’ by 1 if ‘LEFT’ > 0.
- Increase ‘RIGHT’ by 1 if ‘RIGHT’ < ’N’.

- Find the closest non-empty string :
- If the string on ‘MID’ is equal to ‘K’ then do:
- Return 'MID'

- If the string on 'MID' is less than ‘K’ then do:
- ‘START' = 'MID'+1

- If the string on 'MID' is greater than ‘K’ then do:
- 'END' = 'MID'-1.

- Return -1 if we can not find ‘K’.

SIMILAR PROBLEMS

Search In A Sorted 2D Matrix

Posted: 23 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Sort 0s, 1s, 2s

Posted: 24 Dec, 2022

Difficulty: Easy

Day 28 : Fake Coin Problem

Posted: 24 Dec, 2022

Difficulty: Easy

Popular Interview Problems: