Linke und rechte binäre Suche
Problem
Es gibt zwei Listen von Zahlen, die Zahlen in der ersten Liste sind nach Unzerbrechlichkeit geordnet. Bestimmen Sie für jede Zahl in der zweiten Liste die Nummer des ersten und letzten Auftretens dieser Zahl in der ersten Liste.
Eingabe:
- Die erste Zeile der Eingabe enthält zwei Zahlen N und M (\(1<=N,\ M <=20000\));
- Die zweite Zeile enthält N, die nach unauslöschlichen ganzen Zahlen geordnet sind, — Elemente der ersten Liste;
-in der dritten Zeile sind M ganze, nicht negative Zahlen geschrieben - die Elemente der zweiten Liste.
Alle Zahlen in Listen sind ganze 32-Bit-Zeichen.
Ausgabe: das Programm muss M Zeilen ausgeben. Für jede Zahl aus der zweiten Liste muss die Nummer des ersten und letzten Vorkommens in der ersten Liste ausgegeben werden. Die Nummerierung beginnt mit einer Einheit. Wenn die Zahl nicht in der ersten Liste enthalten ist, muss eine Zahl 0 ausgegeben werden.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
|
10 10
3 4
7 7
1 2
0
|