Module: Lineare und binäre Suche nach Elementen in einem Array


Problem

7/7

Implementierung der binären Suche

Theory Click to read/hide

Vergleich von linearen und dualen Suchalgorithmen nach Anzahl der Vergleiche
Beispiele
NeinSuche nach der LinieDoppelsuche
222
ANHANGANHANG5.
1024102411)
ANHANGANHANGANHANG

Plus die Zwei-Wege-Sortierung ist, dass es schneller gemacht wird.
Weniger - Eine vorsortierte Masse ist erforderlich.

Problem

Implementieren Sie einen binären Suchalgorithmus.

Eingaben 
Die erste Zeile der Eingabe enthält natürliche Zahlen N und K (0<N,K<=100000). In der zweiten Zeile werden die N Elemente des ersten Arrays in aufsteigender Reihenfolge angegeben, und in der dritten Zeile– K Elemente des zweiten Arrays. Die Elemente beider Arrays sind ganze Zahlen, von denen jede modulo 109 nicht übersteigt.

Ausgabe 
Es wird für jede der K Zahlen benötigt, um in einer separaten Zeichenfolge" auszugeben;YES", wenn diese Zahl im ersten Array vorkommt, und "NO" andernfalls.
 
Beispiele
№ Eingabe Ausgabe
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!