Binary Search

Lab Java Intermediate 20 points

Read a sorted array and q queries. For each query print its index found by your own iterative 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

Java

Hints

mid = lo + (hi - lo) / 2 avoids overflow for huge arrays.

Solution explanation

Binary search halves the range each step: about 20 steps for a million items.

Show solution

import java.util.Scanner;

public class Main {
    static int search(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] == target) return mid;
            if (a[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int q = sc.nextInt();
        for (int i = 0; i < q; i++) System.out.println(search(a, sc.nextInt()));
    }
}

Output

Answer