Binary Search

Lab C Intermediate 20 points

Read a sorted array and q queries. For each query print its index (binary search) or -1.

Input

n, the sorted integers, q, then q queries.

Output

q lines.

Example

Input

6
1 3 5 7 9 11
3
7
4
11

Output

3
-1
5

Sample input available Sample output available

Editor

Hints

Compare with the middle and discard half of the range.

Solution explanation

An array passed to a function becomes a pointer to its first element (int *a), so the function also needs the length.

Show solution

#include <stdio.h>

int search(int *a, int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    int n, q, x, a[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d", &x);
        printf("%d\n", search(a, n, x));
    }
    return 0;
}

Output

Answer