Module: Ricerca binaria


Problem

1/5

Ricerca binaria nell'array ordinato: start (C++)

Theory Click to read/hide

La ricerca binaria è un efficiente — la sua stima di complessità è O(log2(n)), mentre la ricerca sequenziale convenzionale ha O(n). Ciò significa che, ad esempio, per un array di 1024 elementi, una ricerca lineare, nel caso peggiore, quando l'elemento desiderato non è nell'array, elaborerà tutti i 1024 elementi. La ricerca binaria è sufficiente per elaborare gli elementi \(log_2(1024) = 10\). Questo risultato si ottiene grazie al fatto che dopo il primo passaggio del ciclo, l'area di ricerca si restringe a 512 elementi, dopo il secondo – fino a 256 ecc.

Gli svantaggi di questo algoritmo sono il requisito per l'ordinamento dei dati, nonché la possibilità di accedere a qualsiasi elemento di dati in un tempo costante (indipendente dalla quantità di dati). Pertanto, l'algoritmo non può funzionare su array non ordinati e strutture di dati basate su elenchi collegati.


Attuazione
ciao (destra – sinistra > 1)  // Finché il bordo destro è a destra di sinistra
nc
  centrale = (sinistra + destra) /< /span> 2; // Al centro dell'area di ricerca
  if (A[middle] >= b) allora
    destra = centrale; // Sposta il bordo destro
  altrimenti
    sinistra = centrale; // Altrimenti sposta il bordo sinistro
cc
se (A[right] == X)allora
  uscita destra;
altrimenti
  uscita -1;

dove:
A - matrice sorgente,
N - dimensione dell'array,
X - il numero desiderato.
 

Problem

Implementa un algoritmo di ricerca binaria.
 
Inserisci dati 
La prima riga dell'input contiene i numeri naturali N e K (\(0<N <= 100000,\ 0< K< ;=10^9\) ). La seconda riga contiene gli elementi N dell'array, ordinati in ordine crescente. Gli elementi dell'array sono numeri interi, ciascuno dei quali non supera 109.
 
Uscita
È necessario che  K emetta il suo numero nell'array su una riga separata, se questo numero compare nell'array, e "NO" altrimenti.
 
Esempi
# Input Uscita
1
105
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!