Find it : Easy
Time Limit: 1 sec
Memory Limit: 256 MB
Attempts: 9
Accuracy: 11.11%
Author: Akashdeep Goel
Sheldon and Penny are playing a game where Sheldon gives Penny a long list of positive integers in sorted order and then he asks her to tell the position of different numbers. Faster she answers, more are her chances of winning.
To help her win, Leonard suggest her to use following idea :
1.From the given list, pick up the middle number and check if its smaller or larger than the given number.
2.If its larger then repeat step 1 taking only the upper half of the remaining list.
3.If its smaller then repeat step 1 taking only the lower half of the remaining list.
4.If the middle number is the number to be found, return its position in the list.
5.If the list becomes empty, then the number is not found.
If the number of items in the list is even, then pick the smaller of the 2 middle numbers.
eg suppose the list given is : 1 3 5 7 9 11 13 and we have to find 9 so we start with middle number ie 7. Since 7 is smaller then 9, we consider only the upper part of the list ie : 9 11 13. Now we again take up the middle number from this new list ie 11. Since 11 is larger than 9, we consider only the lower half of the new list ie 9. Since 9 is the number we need to find, we print its position in the original list ie 5
Input :
The first line of input contains two integers N - the number of positive integers in the list and M - the number of numbers whose position Penny has to find.
Next N lines have an integer each, in the order they appear in the list.
Next M lines have the integers whose position is to be found.
Output:
M lines each printing position of the given number in the original list. If the number is not in the list then print "Not Found" (without quotes)
Constraints:
1 ≤ N, M ≤200000
1 ≤ Integers in the list ≤ 100000000;
Example:
Input :
7 2
1
3
5
7
9
11
13
9
12
Output:
5
NOT FOUND
ID
SUBMITTED AT
STATUS
LANGUAGE
TIME
MEMORY USED
USER
TIME
STATUS
LANGUAGE
TIME
MEMORY USED
1 year ago
cpp14
1.00 sec
584 KB
1 year ago
cpp14
0.30 sec
2932 KB
1 year ago
cpp
0.00 sec
0 KB
1 year ago
cpp
1.00 sec
584 KB
1 year ago
cpp14
1.00 sec
704 KB
1 year ago
cpp14
0.99 sec
704 KB
1 year ago
cpp14
1.00 sec
1096 KB
2 years ago
cpp14
1.00 sec
6876 KB
2 years ago
cpp14
1.00 sec
4036 KB