Module: Recherche binaire


Problem

1/5

Recherche binaire dans un tableau ordonné : start (C++)

Theory Click to read/hide

La recherche binaire est une méthode efficace — son estimation de complexité est O(log2(n)), tandis que la recherche séquentielle conventionnelle a O(n). Cela signifie que, par exemple, pour un tableau de 1024 éléments, une recherche linéaire, dans le pire des cas, lorsque l'élément recherché n'est pas dans le tableau, traitera tous les 1024 éléments. La recherche binaire est suffisante pour traiter les éléments \(log_2(1024) = 10\). Ce résultat est obtenu grâce au fait qu'après la première étape de la boucle, la zone de recherche se réduit à 512 éléments, après la seconde – jusqu'à 256 etc.

Les inconvénients de cet algorithme sont la nécessité d'ordonner les données, ainsi que la possibilité d'accéder à n'importe quel élément de données dans un temps constant (indépendamment de la quantité de données). Ainsi, l'algorithme ne peut pas fonctionner sur des tableaux non ordonnés et sur des structures de données basées sur des listes chaînées.


Mise en œuvre
au revoir (droite – gauche > 1)  // Tant que la bordure droite est à droite de la gauche
nc
  milieu = (gauche + droite) /< /span> 2 ; // Milieu de la zone de recherche
  si (A[moyen] >= b)alors
    droite = milieu ; // Déplacer la bordure droite
  autrement
    gauche = milieu ; // Sinon déplacer le bord gauche
cc
si (A[right] == X)alors
  sortie droite ;
autrement
  sortie -1 ;

où :
A - tableau source,
N - taille du tableau,
X - le nombre souhaité.
 

Problem

Mettre en œuvre un algorithme de recherche binaire.
 
Données d'entrée
La première ligne de l'entrée contient les nombres naturels N et K (\(0<N <= 100000,\ 0< K< ;=10^9\) ). La deuxième ligne contient les éléments N du tableau, triés par ordre croissant. Les éléments du tableau sont des entiers, dont chacun ne dépasse pas 109.
 
Sortie
Il est nécessaire que  K affiche son numéro dans le tableau sur une ligne séparée, si ce numéro apparaît dans le tableau, et "NON" sinon.
 
Exemples
105
1 2 3 4 5 6 7 8 9 10
# Entrée Sortie
1 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!