BSEARCH1 - Binary search

no tags 

You are given a sorted array of numbers, and followed by number of queries, for each query if the queried number is present in the array print its position, else print -1.

Input

First line contains N Q, number of elements in the array and number of queries to follow.

Second line contains N numbers, the elements of the array. Each number will be -10^9 <= ai <= 10^9, 0 < N <= 10^5, 0 < Q <= 5*10^5

Output

For each element in the query, print the elements 0 based location of its first occurence, if present, otherwise print -1.

Example

Input:
5 4
2 4 7 7 9
7
10
4
2

Output:
2
-1
1
0

hide comments
expedit0: 2024-06-13 22:51:24

Que exercício da desgraça. Caso façam em C++, usem o I/O mais rápido. Provavelmente é o motivo do TLE

saimur_rahman: 2024-02-21 17:47:23

Use fast I/O and don't use 'endl' in cpp

jqiu: 2024-01-26 11:39:58

AC in 924812849 go !!

imr2357: 2023-09-06 20:41:08

17*5*100000 operations! Should easily pass within 1sec!
But still got TLE due to cin/cout even after using ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
scanf/printf is here to rescue!

ncoaf: 2023-09-02 16:07:10

This problem is bizarre. I used ios_base::sync_with_stdio(false); + cin.tie(NULL); + '\n' instead endl + cin/cout. Check if you take the first occurence of value, this is important.

yant: 2023-04-19 20:34:13

I could only make it work by using lower_bound in cpp

ankiitk: 2021-10-01 17:31:49

complete waste of time,right code but still showing TLE

senapati23: 2020-12-28 18:26:47

Make sure to use scanf and printf for C++ users. The questions asks for the first occurrence of the interger make sure to read the question properly.

leonardovn2525: 2020-07-22 01:34:23

Turns out vedudx is incorrect. This site DOES accept cin and cout, however you need flush your stream. For example, in this problem you could cout <<endl instead of cout << '\n' to flush stuff every time you make a newline. The best option is to use cout.flush() at the end of the program.

Also, use:
ios_base::sync_with_stdio(false);
cin.tie(NULL);

As it makes cin and cout faster than scanf and printf

Last edit: 2020-07-22 02:36:44
cynder: 2020-07-08 23:36:06

Make I/O fast, it cost me some WAs.
Easy problem though, simple binary search.

Last edit: 2020-07-08 23:36:30

Added by:jack(chakradarraju)
Date:2012-03-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:NITT Class