Module: Linear and binary search for elements in an array


Problem

7/7

Binary search implementation

Theory Click to read/hide

Comparison of linear and binary search algorithms by the number of comparisons
 
Examples
# Line Search Binary Search
2 2 2
16 16 5
1024 1024 11
1048576 1048576 21

The advantage of binary sort is that it is faster.
Cons- a pre-sorted array is required.

 

Problem

Implement a binary search algorithm.

Input data 
The first line of the input contains natural numbers N and K (0<N,K<=100000). The second line sets N elements of the first array, sorted in ascending order, and the third line sets – K elements of the second array. The elements of both arrays are integers, each of which does not exceed 109.

Imprint 
It is required for each of K numbers to output in a separate line "YES" if this number occurs in the first array, and "NO" otherwise.
 
Examples
# Input Output
1 10 5
1 2 3 4 5 6 7 8 9 10
-2 0 4 9 12 		NO
NO
YES
YES
NO

 

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below

     

Program check result

To check the solution of the problem, you need to register or log in!