Explication détaillée des compétences javascript half search

Explication détaillée des compétences javascript half search_javascript

WBOY

Libérer： 2016-05-16 16:17:59

original

1801 Les gens l'ont consulté

Méthode de demi-recherche :

Dans une liste ordonnée, lors de la comparaison de la valeur des données à rechercher avec la valeur de l'élément central de la plage de recherche, trois situations se produiront :

1) Si la valeur des données à trouver est exactement égale à la valeur de l'élément du milieu, l'index de la valeur de l'élément du milieu sera renvoyé.

2) Si la valeur des données à rechercher est inférieure à la valeur de l'élément central, la première moitié de toute la plage de recherche sera utilisée comme nouvelle plage de recherche, et 1) sera exécutée jusqu'à ce qu'une valeur égale soit trouvé.

3) Si la valeur des données à rechercher est supérieure à la valeur de l'élément central, alors la seconde moitié de toute la plage de recherche sera utilisée comme nouvelle plage de recherche, et 1) sera exécutée jusqu'à une valeur égale se retrouve

4) Si aucune valeur égale n'est trouvée à la fin, un message d'erreur sera renvoyé.

Compris comme un arbre binaire : la valeur du milieu est la racine de l'arbre binaire, la première moitié est le sous-arbre gauche et la seconde moitié est le sous-arbre droit. Le nombre de recherches pour la méthode de recherche divisée par deux correspond exactement au nombre de niveaux où se trouve la valeur. Dans des conditions de probabilité égale, c'est environ

log2(n 1)-1

Copier le code Le code est le suivant :

//Data est le tableau à rechercher, x est la valeur de données à rechercher, beg est le début de la plage de recherche et last est la fin de la plage de recherche
//Méthode non récursive
int BiSearch(int data[], const int x, int beg, int last)
{
int milieu;//position médiane
Si (mendier > dernier)
{
Retour -1 ;
}
Tandis que (commence <= dernier)
{
         milieu = (commencer en dernier) / 2 ; Si (x == data[mid] )
                                                                                   Retour au milieu
                                                                                                                       else if (data[mid] < x)
                                                                                                   début = milieu 1 ;                                                                                                                                                                        else if (data[mid] > x)
                                                                                   dernier = milieu - 1 ;
                                                                                                              }
Retour -1 ;
}
//Méthode récursive
int IterBiSearch(int data[], const int x, int beg, int last)
{
int milieu = -1 ;
milieu = (commencer en dernier) / 2;
Si (x == data[mid])
{
Retour au milieu
}
sinon si (x < data[mid])
{
         return IterBiSearch(data, x, beg, mid - 1); }
sinon si (x > data[mid])
{
         return IterBiSearch(data, x, mid 1, last
); }
Retour -1 ;
}
//Fonction principale
int _tmain(int argc, _TCHAR* argv[])
{
int données1[60] = {0};
int no2search = 45;
cout << "Le tableau est : " << int taille = taillede(données1)/taillede(int);
pour (int i = 0; i < siz; i )
{
          data1[i] = i;                                      cout << data1[i] << }
cout << fin
indice int = -1 ;
//index = BiSearch(data1, no2search, 0, taille
) Index = IterBiSearch(data1, no2search, 0, taille
) cout << "L'index de " << no2search << est " << Getchar();
Renvoie 0 ;
}

复制代码代码如下 :

/**

* Trouver la position du caractère dans le tableau par moitié (liste ordonnée) 

* @param array Le tableau récupéré

* @param x Le personnage à rechercher 

* @returns La position du caractère dans le tableau, s'il n'est pas trouvé, renvoie -1 

​*/  

function binaireRecherche(array,x){ 

  varPointBas=1;                     

 var higPoint=array.length;

 var returnValue=-1;                

 var point médian ;

 var trouvé = faux ;                   

 while ((lowPoint<=higPoint)&&(!found)){

  midPoint=Math.ceil((lowPoint higPoint)/2); 

  //console.log(lowPoint "====" midPoint "====" highPoint);

  si(x>array[midPoint-1]){

   point bas=point médian 1;

  >

  sinon if(x
   higPoint= midPoint-1;

  >

  sinon if(x=array[midPoint-1]){

   trouvé=true;

  >

 } 

 si(trouvé){

    returnValue=midPoint;

 >

 return returnValue;

>

/*var array2=[1,2,3,4,5,6,7,8,9,100,109];*/

var array2=['a','b','c','d','e','f','g'];

console.log(binarySearch(array2,'c'));