Read n different numbers in increasing order, then q queries. For each query x, print the index of x in the array (counting from 0), or -1 if it is not there. Use binary search.
What to build
A search that answers each query by halving a sorted array.
Requirements
- Keep a range that must contain the key if it is there at all.
- Compare with the middle item and throw away the half that cannot contain the key.
- Print -1 when the range becomes empty.
Input
The first line has n (1 ≤ n ≤ 1000) and the second line the n numbers in increasing order. The third line has q (1 ≤ q ≤ 1000) and the fourth line the q queries.
Output
One line per query: the index, or -1.
Constraints
1 ≤ n ≤ 1000, 1 ≤ q ≤ 1000, and the numbers are all different and increasing.
Example
Input:
5
2 4 6 8 10
3
6 7 2
Output:
2
-1
0
Why it works
Each comparison halves the range, so 1000 numbers need at most about 10 comparisons per query.
Examples
5 2 4 6 8 10 3 6 7 2
2 -1 0
1 5 2 5 6
0 -1
Hints
Hint 1
Keep a range lo .. hi that must contain the key, starting with 0 .. n - 1.
Hint 2
Compare with a[mid]: equal means found; smaller means search right (lo = mid + 1); larger means search left (hi = mid - 1).
Hint 3
When lo > hi, the key is not there.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int binary_search(int a[], int n, int key) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == key) return mid;
if (a[mid] < key) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
int main(void) {
int n, q;
int a[1000];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &q);
for (int i = 0; i < q; i++) {
int x;
scanf("%d", &x);
printf("%d\n", binary_search(a, n, x));
}
return 0;
}