Upper Bound
Practice this coding question on Coding Gurukul.
Problem statement
Given an array sorted in nondecreasing order and q query values, answer each query x. For each query, print the first index i where a[i] > x. If no such index exists, print n. Indices are zero-based. Duplicate values are allowed. Do not change the array. Use binary search in O(log n) time per query. For an empty array, print 0 for every query. Worked example For [1, 3, 3, 7, 9], queries 3, 6 and 9 give 3, 3 and 5. No value is greater than 9, so its answer is n=5.
Input format
First line: n q. Second line: n sorted integers (empty for n=0). Next q lines: one query value x each.
Output format
Print the result for each query on a separate line.
Constraints
0 <= n <= 100000; 1 <= q <= 100000; -10^9 <= a[i],x <= 10^9.
Sample input
5 3 1 3 3 7 9 3 6 9
Sample output
3 3 5
Sign in to run or submit a solution in C++, Java or Python.