-
Notifications
You must be signed in to change notification settings - Fork 2
/
Binary_srch_first_occurenc.py
61 lines (54 loc) · 1.03 KB
/
Binary_srch_first_occurenc.py
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution:
# @param A : list of integers
# @return a list of integers
def bin1(self, A,Q):
s = 0
e = len(A)-1
x = -1
while s<=e:
m = int((e+s)/2)
if A[m]==Q:
x = m
e = m-1 #for the first occurence, s=m+1 for the last occurence
elif A[m]<Q:
s = m+1
elif A[m]>Q:
e = m-1
return x
if __name__=='__main__':
B =Solution()
#n = int(input())
n = input().split(' ')
#lst = tuple(map(int,input().split(' ')))
lst = input().split(' ')
lst = tuple(map(int,lst))
for i in range(int(n[1])):
#c = list(map(int,input().split(' ')))
q = int(input())
print (B.bin1(lst,q))
exit
'''
Find the first occurence of any given number.
Input
K N
0 1 .... K (elements)
0
1
.
.
N (Queries)
Output
Index of first occurence of the number, -1 if num doesnot exist
example:-
5 4
0 1 1 2 2
1
2
3
0
output:-
1
3
-1
0
'''