Challenge: Binary Search

Lab Python Beginner 10 points

Read a sorted list of numbers and then q numbers to look for. For each one print its position (index from 0), or -1. Write the binary search yourself.

Input

Line 1: sorted whole numbers, all different. Line 2: q. Line 3: q numbers.

Output

One position per query.

Example

Input

3 8 15 21 34 42
4
42 3 5 34

Output

Sample input available Sample output available

Editor

Python

Hints

Keep low and high; look at mid = (low + high) // 2.

Move low up or high down depending on the comparison.

Solution explanation

Each query takes O(log n) steps instead of O(n).

Show solution

def search(a, t):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == t:
            return mid
        if a[mid] < t:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

a = list(map(int, input().split()))
q = int(input())
for t in map(int, input().split()):
    print(search(a, t))

Output

Answer