Pliez la méthode à moitié d'abondance :
Dans un tableau ordonné, comparez la valeur des données à rechercher avec la valeur d'élément intermédiaire de la plage de recherche, et il y aura trois situations:
1) Si la valeur des données à trouver est exactement égale à la valeur d'élément intermédiaire, remettez l'index de la valeur d'élément intermédiaire.
2) Si la valeur de données à rechercher est inférieure à la valeur de l'élément intermédiaire, utilisez la première moitié de la plage de recherche entière comme nouvelle plage de recherche et exécutez 1) jusqu'à ce qu'une valeur égale soit trouvée.
3) Si la valeur de données à rechercher est supérieure à la valeur de l'élément intermédiaire, utilisez la seconde moitié de la plage de recherche entière comme nouvelle plage de recherche et exécutez 1) jusqu'à ce que la valeur égale soit trouvée.
4) Si la même valeur ne peut pas être trouvée à la fin, un message d'erreur sera renvoyé.
Selon l'arbre binaire, la valeur moyenne 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 à moitié d'abondance est exactement le nombre de couches où se trouve la valeur. Sous une probabilité égale, approximativement
log2 (n + 1) -1
La copie de code est la suivante:
// Les données sont le tableau à rechercher, x est la valeur des données à rechercher, Beg est le début de la plage de recherche, et le dernier est la fin de la plage de recherche
// Méthode non réécitée
int bissearch (int data [], const int x, int Beg, int dernier)
{
int mid; // position intermédiaire
si (Beg> dernier)
{
retour -1;
}
tandis que (Beg <= dernier)
{
mid = (Beg + dernier) / 2;
if (x == data [mid])
{
retour à mi-chemin;
}
else if (data [mid] <x)
{
BEG = mid + 1;
}
else if (data [mid]> x)
{
Dernier = Mid - 1;
}
}
retour -1;
}
// Méthode récursive
int iterBiSearch (int data [], const int x, int Beg, int dernier)
{
int mid = -1;
mid = (Beg + dernier) / 2;
if (x == data [mid])
{
retour à mi-chemin;
}
else if (x <data [mid])
{
return iterBiSearch (données, x, Beg, mi-1);
}
else if (x> data [mid])
{
return iterBiSearch (data, x, mid + 1, dernier);
}
retour -1;
}
// fonction principale
int _tmain (int argc, _tchar * argv [])
{
int data1 [60] = {0};
int no2Search = 45;
cout << "Le tableau est:" << endl;
int siz = sizeof (data1) / sizeof (int);
pour (int i = 0; i <siz; i ++)
{
data1 [i] = i;
cout << data1 [i] << "";
}
cout << endl;
int index = -1;
// index = bissearch (data1, no2search, 0, siz);
index = iterBiSearch (data1, no2search, 0, siz);
cout << "Index de" << no2search << "est" << index << endl;
getChar ();
retour 0;
}
La copie de code est la suivante:
/ **
* À moitié pour trouver la position des caractères dans le tableau (liste ordonnée)
* @param tableau le tableau récupéré
* @param x caractères à trouver
* @returns la position du caractère dans le tableau, aucun retour trouvé -1
* /
fonction binarysearch (array, x) {
var lowpoint = 1;
var higpoint = array.length;
var returnValue = -1;
var midpoint;
var trouvé = false;
while ((lowpoint <= higpoint) && (! trouvé)) {
midpoint = math.ceil ((Lowpoint + HigPoint) / 2);
//console.log(lowpoint+"===="+midpoint+"===="+higpoint);
if (x> array [midpoint-1]) {
LowPoint = point médian + 1;
}
else if (x <array [midpoint-1]) {
HigPoint = midpoint-1;
}
else if (x = array [midpoint-1]) {
Found = true;
}
}
if (trouvé) {
returnValue = midpoint;
}
retour 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»));