Module: Binäre Suche


Problem

1/5

Binäre Suche in einem geordneten Array: Anfang (C++)

Theory Click to read/hide

Die duale Suche ist ein effektiver Algorithmus - seine Bewertung der Komplexität O(log2(n))zu einer Zeit wie eine Routine, konsequente Suche O(n)♪ Dies bedeutet, dass beispielsweise für einen Satz von 1.024 Elementen eine lineare Suche, im schlimmsten Fall, wenn das Anspruchselement nicht in der Masse ist, alle 1024 Elemente abdeckt. Binärsuche ist genug \(log_2(1024) = 10\) Elemente. Dieses Ergebnis wird erreicht, indem der Suchbereich nach dem ersten Schritt des Zyklus auf 512 Elemente reduziert wird, nach dem zweiten Schritt auf 256, etc.

Fehlen eines solchen Algorithmus ist die Anforderung der Konsistenz der Daten, sowie die Möglichkeit des Zugriffs auf jedes dauerhafte (nicht-Daten) Datenelement. Somit kann der Algorithmus nicht an unregulierten Massen und Datenstrukturen arbeiten, die auf einer Linkliste aufgebaut sind.


Durchführung
HTML generiert mit Hilite. ich 
Tschüss. (rechts) ation 1) / Solange die rechte Linie rechts nach links ist.ZMitte = (links) + Recht / 2; / Suchbereich wenn (A[Mitte) │ (b)♪Recht = Mittel; / Die richtige Linie verschieben Anderelinks = Mittel; / Ansonsten bewegen wir die linke Linie.Knospenwenn (A[rechts]) == sync, berichtigt von elderman == X♪Fazit des Rechts;
AndereSchlußfolgerung -1;

Wo:
А - die Referenzmasse,
N Größe der Masse,
X - Nummer.

Problem

Implementieren Sie einen binären Suchalgorithmus.
 
Eingaben 
Die erste Zeile der Eingabe enthält die natürlichen Zahlen N und K (\(0<N <= 100000,\ 0<K<=10^9\) ). In der zweiten Zeile werden die N Elemente des Arrays in aufsteigender Reihenfolge angegeben. Die Elemente des Arrays sind ganze Zahlen, von denen jede modulo 109 nicht übersteigt.
 
Ausgabe
Es ist erforderlich, dass K seine Nummer im Array in einer separaten Zeichenfolge ausgibt, wenn diese Zahl im Array vorkommt, und " andernfallsNO.
 
Beispiele
№ Eingabe Ausgabe
1
10 5
1 2 3 4 5 6 7 8 9 10 
 5

time 1000 ms
memory 32 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 
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int Search_Binary (vector<int> arr, int key)
{
	int  midd = 0, left =-1, right = arr.size();

                   
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, w, h, l, r, k, index;

	cin >> n >> k;

	vector<int> A(n);

	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}

       index = Search_Binary (A, k);
 
	if (index >= 0) 
		cout << index+1;
	else
		cout << "NO";
}

     

Program check result

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