All submissions for this problem are available.
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
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.
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)
- 1 ≤ N,M ≤ 200000
- 1 ≤ Integers in the list ≤ 100000000
Input: 7 2 1 3 5 7 9 11 13 9 12 Output: 5 NOT FOUND
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.