Binary Search
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 index of the first occurrence of x. If x is absent, print -1. 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 -1 for every query. Worked example For [1, 3, 3, 7, 9], queries 3, 6 and 9 give 1, -1 and 4.
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
1 -1 4
Sign in to run or submit a solution in C++, Java or Python.