Rekursive Binärsuche
Manchmal ist es sehr praktisch, die Binärsuche rekursiv zu implementieren. Sie sollen eine Binärsuchfunktion schreiben, die den Index des am weitesten links stehenden
target-Elements im Array zurückgibt, sofern dieses gefunden wird, oder andernfalls -1.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n (1 ≤ n ≤ ), die die Anzahl der Elemente angeben, sowie q (1 ≤ q ≤ ) für die Anzahl der Abfragen.Die nächste Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen ( ≤ ≤ ) in aufsteigender Reihenfolge.Die letzte Zeile enthält
q durch Leerzeichen getrennte ganze Zahlen ( ≤ ≤ ), die Zielwerte für die Suche.Ausgabe
Das Programm soll
q ganze Zahlen ausgeben, die das Ergebnis für jeden Zielwert repräsentieren (die Indizes beginnen bei 0).Beispiele
Eingabe | Ausgabe |
9 3
20 22 23 23 34 49 52 55 58
49 22 24 | 5 1 -1 |
Constraints
Time limit: 8 seconds
Memory limit: 512 MB
Output limit: 1 MB