Module: Recherche linéaire et binaire d'éléments dans un tableau


Problem

6/7

Recherche binaire

Theory Click to read/hide

Recherche binaire
La recherche binaire (ou binaire) est un algorithme de recherche efficace et plus rapide que la recherche linéaire. 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 les 1024 éléments, mais il suffit de traiter 10 éléments avec une recherche binaire. 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épendant de la quantité de données). Par conséquent, l'algorithme ne peut pas fonctionner sur des tableaux non ordonnés.
 
Algorithme
  1. Sélectionnez l'élément intermédiaire A[c] et comparez avec X.
  2. Si X = A[c] alors trouvé (stop).
  3. Si X < A[c], chercher plus loin dans la première moitié.
  4. Si X > A[c], regardez plus loin dans la seconde moitié.
     
Mise en œuvre
L = 0 ; R=N; // segment initial tandis que ( L < R - 1) { c = (L + R) / 2 ; // a trouvé le milieu if ( X < A[c] ) // compression de segment R=c; autre L = c ; } si ( A[L] == X) cout << "A" << L<< "]=" << X; autre cout << "Introuvable";

où :
A - tableau source,
N - taille du tableau,
X - numéro recherché,

D'autres implémentations sont possibles.
Par exemple, en utilisant une sortie anticipée de la boucle L = 0 ; R = N-1 ; tandis que (R >= L) { c = (L + R) / 2 ; si ( X == A[c] ) { nX = c ; casser; } si (X < ; A[c]) R = milieu - 1 ; si (X > A[c]) L = milieu + 1 ; } si ( nX < 0) cout << "Non trouvé"; autre cout << "A" << nX<< "]=" << X ;

Problem

Dans le tableau donné, trié par ordre croissant, vous devez trouver la valeur de l'élément égale à la valeur X en utilisant la recherche binaire. X est saisi au clavier. Modifier le programme pour qu'il résolve le problème La numérotation des éléments commence à zéro. S'il n'y a pas un tel élément, le programme doit afficher Not found.

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 
#include<iostream> 
using namespace std; 
main() 
{	
  const int Nmax=1000; 	
  int A[Nmax], i, L, R, X, N, c;	 
  cin >> N; 
  for (i=0; i<N; i++) 
    cin >> A[i]; 
  cin >> X; 
  L = 0; R = N;       
  while ( L < R-1 )     
       cout << "A["<< L << "]=" << X; 
  else cout << "Not found"; 
}

     

Program check result

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