1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
# Uses python3
import sys
# def binarySearchRecursive(a, low, high, key):
# if high < low:
# return -1
# mid = (int) (low + (high - low) / 2)
# if key == a[mid]:
# return mid
# elif key < a[mid]:
# return binarySearchRecursive(a, low, mid - 1, key)
# else:
# return binarySearchRecursive(a, mid + 1, high, key)
def binarySearchIterative(a, low, high, key):
while low <= high:
mid = (int) (low + (high - low)/2)
if key == a[mid]:
return mid;
elif key < a[mid]:
high = mid - 1
else:
low = mid + 1
return -1
def binarySearch(a, key):
# return binarySearchRecursive(a, 0, len(a) - 1, key)
return binarySearchIterative(a, 0, len(a) - 1, key)
if __name__ == '__main__':
input = sys.stdin.read()
data = list(map(int, input.split()))
n = data[0]
m = data[n + 1]
a = data[1 : n + 1]
for x in data[n + 2:]:
print(binarySearch(a, x), end = ' ')
|
