Recursive Binary Search
Sometimes it’s very convenient to implement the binary search recursively. You’re asked to implement a binary search function that would return the index of the leftmost
target element from the array if it was found and -1 otherwise.Input
The first line of the input contains two integers
n (1 ≤ n ≤ ) the number of elements and q (1 ≤ q ≤ ) the number of queries.The next line contains
n space-separated integers ( ≤ ≤ ) in increasing order.The last line contains
q space-separated integers ( ≤ ≤ ) the target values.Output
The program should print
q integers representing the result for the corresponding target value (the indexing starts from 0).Examples
Input | Output |
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