discover-the-monk

You are given an array A of size N, and Q queries to deal with. For each query, you are given an integer X, and you're supposed to find out if X is present in the array A or not.

Input:
The first line contains two integers, N and Q, denoting the size of array A and number of queries. The second line contains N space separated integers, denoting the array of elements Ai. The next Q lines contain a single integer X per line.

Output:
For each query, print YES if the X is in the array, otherwise print NO.

Constraints:
1 ≤ N, Q ≤ 10^5
1 ≤ Ai ≤ 10^9
1 ≤ X ≤ 10^9

SAMPLE INPUT
5 10
50 40 30 20 10
10
20
30
40
50
60
70
80
90
100

SAMPLE OUTPUT
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO

Difficulty: EASY
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
def bin_srch(A,X):
	lo=0
	hi=len(A)
	while(lo<hi):
		mid=(lo+hi)//2
		midval=A[mid]
		if midval<X:
			lo=mid+1
		elif midval>X:
			hi=mid
		else:
			return mid
	return -1


if __name__=="__main__":
	N,Q=list(map(int,input().split()))
	A=[int(x) for x in input().split()]
	A.sort()
	for i in range(Q):
		X=eval(input())
		if bin_srch(A,X)!=-1:
			print("YES")
		else:
			print("NO")




'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'

def Bsearch(arr, beg, end, val):
	if beg <= end:
		mid = (beg+end)/ 2
		if arr[mid] == val:
			print('YES')
			return
		elif arr[mid] > val:
			Bsearch(arr, beg, mid-1, val)
		elif arr[mid] < val:
			Bsearch(arr, mid+1, end, val)
	else:
		print('NO')
n , q = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()

for i in range(q):
	num = eval(input())
	if num < A[0] and num > A[n-1]:
		print('NO')
	else:
		Bsearch(A, 0, n-1, num)
	# 	print 'YES'
	# else:
	# 	print 'NO'


def bsearch(arr , n , num):
	l , r = 0 , n-1
	while l <= r:
		mid = (l+r)/2
		if arr[mid] == num:
			return 1
		elif arr[mid] > num:
			r = mid - 1
		else:
			l = mid + 1
	return 0
n , q = list(map(int , input().split()))
arr = list(map(int , input().split()))
arr = sorted(arr)
for i in range(q):
	num = int(input())
	if bsearch(arr , n , num):
		print("YES")
	else:
		print("NO")


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''


arr_inp=[]
for j in input().split(' '):
	arr_inp.append(int(j))

#line2 = raw_input()
elemnt_array = {}
for i in input().split(' '):
	elemnt_array[int(i)] = '1'
#elemnt_array.sort()
#print elemnt_array, "and quries are", arr_inp[1]
for i in range (arr_inp[1]):
	if int(input()) in elemnt_array:
		print("YES")
	else:
		print("NO")


def binarySearch(alist, item):
	first = 0
	last = len(alist)-1
	found = False

	while first<=last and not found:
		midpoint = (first + last)//2
		if alist[midpoint] == item:
			found = True
		else:
			if item < alist[midpoint]:
				last = midpoint-1
			else:
				first = midpoint+1

	return found

a = input().split()
c = int(a[1])
b = sorted([int(i) for i in input().split()])

for k in range(c):
	a = int(input())
	if binarySearch(b, a):
		print("YES")
	else:
		print("NO")


'''
You are given an array A of size N, and Q queries to deal with. For each query, you are given an integer X, and you're supposed to find out if X is present in the array A or not.

Input:
The first line contains two integers, N and Q, denoting the size of array A and number of queries. The second line contains N space separated integers, denoting the array of elements Ai. The next Q lines contain a single integer X per line.

Output:
For each query, print YES if the X is in the array, otherwise print NO.

Constraints:
1 <= N, Q <= 105
1 <= Ai <= 109
1 <= X <= 109

SAMPLE INPUT
5 10
50 40 30 20 10
10
20
30
40
50
60
70
80
90
100
SAMPLE OUTPUT
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
'''

def merge_sort(items):
	#print 'Inside merge_sort: {0}'.format(items)
	if len(items) == 1:
		return items

	if len(items) > 1:
		mid = len(items) / 2
		left = items[:mid]
		right = items[mid:]

		merge_sort(left)
		merge_sort(right)

		i,j,k = 0,0,0

		while i < len(left) and j < len(right):
			if left[i] > right[j]:
				items[k] = left[i]
				i += 1
			else:
				items[k] = right[j]
				j += 1
			k += 1

		while i < len(left):
			items[k] = left[i]
			i += 1
			k += 1
		while j < len(right):
			items[k] = right[j]
			j += 1
			k += 1

	return items

def binary_search(items, start, end, search_item):
	#print items

	if start <= end:

		#start = 0
		#end = len(items) - 1
		mid = start + (end - start) / 2

		if items[mid] == search_item:
			print('YES')
		elif items[mid] > search_item:
			binary_search(items, mid + 1, end, search_item)
		else:
			binary_search(items, start, mid - 1, search_item)

	else:
		print('NO')


def check_number_in_list():
	size_of_array, no_of_queries = [int(x) for x in input().split(' ')]
	items = [int(x) for x in input().split(' ')] #This array needs to be sorted before applying for binary_search
	#print 'Before sorting {0}'.format(items)
	merge_sort(items)
	#print 'After sorting {0}'.format(items)
	for _ in range(no_of_queries):
		search_item = int(input())
		binary_search(items, 0, len(items)-1, search_item)

check_number_in_list()




N, Q = list(map(int, input().split()))
A = list(map(int,input().split()))
A.sort()

def binary_s(low, high, val):
	if low==high:
		return low

	mid = (low+high)>>1
	if A[mid]>val:
		high = mid
		return binary_s(low, high, val)	
	else:
		if low == mid:
			return low
		low = mid
		return binary_s(low, high, val)

for q in range(Q):
	q = eval(input())
	if q >= A[0] and q <= A[N-1]:
		a_index = binary_s(0, N, q)
		if A[a_index] == q:
			print('YES')
		else:
			print('NO')	
	else:
		print('NO')



def binary_search(array,left,right,value):
	mid = (left + right)/2
	if(right>=left):
		if array[mid] == value:
			return 'YES'
		elif array[mid]>value:
			return binary_search(array,left,mid-1,value)
		else:
			return binary_search(array,mid+1,right,value)
	else:
		return 'NO'

n,q=list(map(int,input().split(" ")))
array=list(map(int,input().split(" ")))
array.sort()
query=[]
for i in range(q):
	query.append(eval(input()))
for each in query:
	print(binary_search(array,0,n-1,each))


def binary_search(a,num):
	first=0
	last=len(a)-1 
	while(first<=last):
		mid=(first+last)//2
		if a[mid]==num:
			return mid
		elif a[mid]>num:
			last=mid-1
		else:
			first=mid+1
	return -1

var=list(map(int,input().split()))
n=var[0]
m=var[1]
l=list(map(int,input().split()))
l.sort()
for i in range(0,m,1):
	k=int(eval(input()))
	c=binary_search(l,k)
	if c==-1:
		print("NO")
	else:
		print("YES")



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'

def Bsearch(arr, beg, end, val):
	if beg <= end:
		mid = (beg+end)/ 2
		if arr[mid] == val:
			print('YES')
			return
		elif arr[mid] > val:
			Bsearch(arr, beg, mid-1, val)
		elif arr[mid] < val:
			Bsearch(arr, mid+1, end, val)
	else:
		print('NO')
n , q = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()

for i in range(q):
	num = eval(input())
	if num < A[0] and num > A[n-1]:
		print('NO')
	else:
		Bsearch(A, 0, n-1, num)
	# 	print 'YES'
	# else:
	# 	print 'NO'


def binarySearch(alist, item):
	    first = 0
	    last = len(alist)-1
	    found = False
	
	    while first<=last and not found:
	        midpoint = (first + last)/2
	        if alist[midpoint] == item:
	            found = True
	        else:
	            if item < alist[midpoint]:
	                last = midpoint-1
	            else:
	                first = midpoint+1
	
	    return found
	    
def binary():
	n, q = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	for i in range(q):
		b = int(input())
		
		if binarySearch(a, b):
			print('YES')
		else:
			print('NO')

if __name__ == "__main__":
	binary()


def bSearch(listi,low,high,x):
	mid=(low+high+1)/2
	while(low<high):
		if listi[mid]==x:
			return True
		elif listi[mid]<x:
			return bSearch(listi, mid+1, high, x)
		else:
			return bSearch(listi, low, mid-1, x)
	if low==high:
		return listi[low]==x
		
inp=[int(i) for i in input().split()]
n=inp[0]
q=inp[1]
listi=[int(i) for i in input().split()]
listi.sort()
for i in range(q):
	t=eval(input())
	if bSearch(listi,0,len(listi)-1,t):
		print("YES")
	else:
		print("NO")


n, q = [int(s) for s in input().split()]
arr = sorted([int(s) for s in input().split()])
for _ in range(q):
	x = eval(input())
	start = 0
	end = len(arr)-1
	while start <= end:
		mid = start + (end-start)/2
		if arr[mid] == x:
			print('YES')
			break
		if arr[mid] > x:
			end = mid-1
		else:
			start = mid+1
	else:
		print('NO')


def is_present(nums, x):
	i = 0
	j = len(nums) - 1
	
	while i <= j:
		mid = (i + j) / 2
		if nums[mid] == x:
			return 'YES'
		elif nums[mid] < x:
			i = mid + 1
		else:
			j = mid - 1
	
	return 'NO'

N, Q = list(map(int, input().split()))
nums = list(map(int, input().split()))
nums.sort()

for i in range(Q):
	x = eval(input())
	print(is_present(nums, x))


def bin_search(a,k):
	lb=0
	ub=len(a)-1
	mid=(lb+ub)//2
	#print mid
	while(lb<=ub):
		mid=(lb+ub)//2
		if k>a[mid]:
			lb=mid+1
		elif k<a[mid]:
			ub=mid-1
		elif k==a[mid]:
			return True
		#print lb,ub,mid
	return False
			


s=input()
n=int(s.split(' ')[0])
q=int(s.split(' ')[1])
a=[]
a=list(map(int,input().split(' ')))
#print a
a.sort()
while q>0:
	k=int(input())
	if bin_search(a,k):
		print("YES")
	else:
		print("NO")
	q-=1


def bin(a,n):
	start=0
	end=len(a)-1
	while True:
		if end<start:
			return -1
		mid=(start+end)//2
		if n<a[mid]:
			 end=mid-1
		elif n>a[mid]:
			 start=mid+1
		elif n==a[mid]:
			#print 'element found at index %d'%mid
			return 1
n,q=[int(i) for i in input().split()]
x=[int(i) for i in input().split()]
x.sort()
Q=[]
for i in range(q):
	t=int(input())
	Q.append(t)
for i in Q:
	if bin(x,i)==1:
		#print x,i
		print('YES')
	else:
		print('NO')


def query(N,Nsize,line_query):    
	low=0
	high=Nsize-1
	while(low<=high):
		mid=(low+high)//2
		if(N[mid]>line_query):
			high = mid-1
		elif(N[mid]<line_query):
			low = mid+1
		else:
			return "YES"
			break
	return "NO"

if __name__ == "__main__":
	testcases =  input()
	N=testcases.split(" ")
	Narray = list(map(int,input().split()))
	Narray.sort()
	for caseNr in range(1, int(N[1])+1):          
		line_query = int(input())
		print(query(Narray,int(N[0]),line_query))
		


from collections import defaultdict
d=defaultdict(int)
a=[]
n,m=list(map(int,input().split()))
a=list(map(int,input().strip().split()))
for i in a:
	d[i]+=1
for i in range(m):
	k=eval(input())
	if k in d:
		print("YES")
	else:
		print("NO")
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

line1 = input()
arr_inp=[]
for j in line1.split(' '):
	arr_inp.append(int(j))

#line2 = raw_input()
elemnt_array = {}
for i in input().split(' '):
	elemnt_array[int(i)] = 1
#elemnt_array.sort()
#print elemnt_array, "and quries are", arr_inp[1]
for i in range (arr_inp[1]):
	if int(input()) in elemnt_array:
		print("YES")
	else:
		print("NO")


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

line1 = input()
arr_inp=[]
for j in line1.split(' '):
	arr_inp.append(int(j))
line2 = input()
elemnt_array = {}
for i in line2.split(' '):
	elemnt_array[int(i)] = 1
#elemnt_array.sort()
#print elemnt_array, "and quries are", arr_inp[1]
for i in range (arr_inp[1]):
	if int(eval(input())) in elemnt_array:
		print("YES")
	else:
		print("NO")


__author__ = 'ankur'


def binary_search_recursive(listi, low, high, x):
	mid = low + (high - low) / 2
	if low <= high:
		if listi[mid] == x:
			return True
		elif listi[mid] < x:
			return binary_search_recursive(listi, mid + 1, high, x)
		else:
			return binary_search_recursive(listi, low, mid - 1, x)
	return False


inp = [int(i) for i in input().split()]
N = inp[0]
Q = inp[1]
A = [int(i) for i in input().split()]
A.sort()
for i in range(Q):
	x = eval(input())
	if binary_search_recursive(A, 0, len(A) - 1, x):
		print("YES")
	else:
		print("NO")


n, q = [int(s) for s in input().split()]
arr = set([int(s) for s in input().split()])
for _ in range(q):
	print('YES' if eval(input()) in arr else 'NO')


def bs(arr,se,l,r):
	if l<=r:
		mid=(l+r)/2
		if se==arr[mid]:
			return "YES"
		elif se<arr[mid]:
			return bs(arr,se,l,mid-1)
		elif se>arr[mid]:
			return bs(arr,se,mid+1,r)
	else:
		return "NO"


n,q=list(map(int,input().split()))
arr=list(map(int,input().split()))
arr=sorted(arr)
while q>0:
	x=eval(input())
	if x>=arr[0] and x<=arr[-1]:
		print(bs(arr,x,0,n))
	else:
		print("NO")
	q-=1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def discover_the_monk(array, left,right,x):
	if left <= right:
		mid = left + ( right - left ) / 2
		if array[mid] == x:
			return 'YES'
		elif x > array[mid]:
			return discover_the_monk(array, mid + 1, right, x)
		else:
			return discover_the_monk(array, left, mid-1, x)
	else:
		return 'NO'

if __name__ == "__main__":
	n,q = list(map(int, input().split()))
	array = sorted(map(int, input().split()))
	mini, maxi = array[0], array[-1]
	for _ in range(q):
		x = int(input())
		print(discover_the_monk(array, 0,n-1, x))


from collections import defaultdict
N,Q = [int(x) for x in input().split()]
dicti = defaultdict(int)
arr = [int(x) for x in input().split()]
for i in arr:
	dicti[i]=1

for i in range(Q):
	x  = int(input())
	if dicti[x]==1:
		print("YES")
	else:
		print("NO")


def binarysearch(a,t):
	low=0
	high=len(a)-1
	while low<=high:
		mid=(low+high)/2
		if t==a[mid]:
			#print mid
			return True
		elif t<a[mid]:
			high=mid-1
		else:
			low=mid+1
	return False



n,q=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
i=0
while i<q:
	t=eval(input())
	if binarysearch(a,t):
		print("YES")
	else:
		print("NO")
	i+=1


a=input()
a=a.split()
a=list(map(int,a))
b=input()
b=list(map(int,b.split()))
b.sort()

def search(n):
	low=0
	high=len(b)-1
	while high>=low:
		mid = (high+low)/2
		if b[mid]==n:
			return True
		elif b[mid]<n:
			low=mid+1
		elif b[mid]>n:
			high=mid-1
	return False

while a[1]>0:
	c=eval(input())
	if search(c):
		print('YES')
	else:
		print('NO')
	a[1]=a[1]-1



from collections import defaultdict
d=defaultdict(int)
a=[]
n,m=list(map(int,input().split()))
a=list(map(int,input().strip().split()))
for i in a:
	d[i]+=1
for i in range(m):
	k=eval(input())
	if d[k]>0:
		print("YES")
	else:
		print("NO")
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'

def Bsearch(arr, beg, end, val):
	if beg <= end:
		mid = (beg+end)/ 2
		if arr[mid] == val:
			print('YES')
			return
		elif arr[mid] > val:
			Bsearch(arr, beg, mid-1, val)
		elif arr[mid] < val:
			Bsearch(arr, mid+1, end, val)
	else:
		print('NO')
n , q = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort()

for i in range(q):
	num = eval(input())
	if num < A[0] and num > A[n-1]:
		print('NO')
	else:
		Bsearch(A, 0, n-1, num)
	# 	print 'YES'
	# else:
	# 	print 'NO'


def binary_search(list, query):

	i = 0
	j = len(list)-1

	while i<=j:

		mid = (i+j)/2

		if query == list[mid]:
			return 'YES'
		elif query < list[mid]:
			j = mid-1
		else:
			i = mid+1

	return 'NO'


test_cases, queries = input().split()

arr = input().split()
arr = [int(x) for x in arr]

arr.sort()

queries = int(queries)

i = 0
while i < queries:
	query = int(input())

	print(binary_search(arr,query))

	i += 1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

line1 = input()
arr_inp=[]
for j in line1.split(' '):
	arr_inp.append(int(j))

#line2 = raw_input()
elemnt_array = {}
for i in input().split(' '):
	elemnt_array[int(i)] = '1'
#elemnt_array.sort()
#print elemnt_array, "and quries are", arr_inp[1]
for i in range (arr_inp[1]):
	if int(input()) in elemnt_array:
		print("YES")
	else:
		print("NO")


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

line1 = input()
arr_inp=[]
for j in line1.split(' '):
	arr_inp.append(int(j))

#line2 = raw_input()
elemnt_array = {}
for i in input().split(' '):
	elemnt_array[i] = 1
#elemnt_array.sort()
#print elemnt_array, "and quries are", arr_inp[1]
for i in range (arr_inp[1]):
	if input() in elemnt_array:
		print("YES")
	else:
		print("NO")