Comment implémenter une recherche binary dynamic pour les opérations de recherche et d’insertion de n élément

L’idée est d’utiliser plusieurs tableaux, chacun d’une longueur de 2 ^ k, pour stocker n éléments, conformément à la représentation binary de n.Chaque tableau est sortingé et les différents tableaux ne sont en aucun cas ordonnés.

Dans la structure de données susmentionnée, la recherche est effectuée par une séquence de recherche binary sur chaque tableau. INSERT est réalisé par une séquence de fusion de tableaux de même longueur jusqu’à atteindre un tableau vide.

Plus de détail: Supposons que nous ayons un tableau vertical de longueur 2 ^ k et que chaque noeud de ce tableau y soit associé un tableau horizontal de longueur 2 ^ k.

C’est-à-dire qu’au premier noeud du tableau vertical, un tableau horizontal de longueur 2 ^ 0 = 1 est connecté, au deuxième noeud du tableau vertical, à un tableau horizontal de longueur 2 ^ 1 = 2 et ainsi de suite. Donc, l’insertion est d’abord effectuée dans le premier tableau horizontal, pour le deuxième insert, le premier tableau devient vide et le deuxième tableau horizontal est plein avec 2 éléments, pour le troisième insert, le premier et le second tableau horiz. tableau sont remplis et ainsi de suite. J’ai implémenté la recherche binary normale pour search et insert comme suit:

int main() { int a[20]= {0}; int n, i, j, temp; int *beg, *end, *mid, target; printf(" enter the total integers you want to enter (make it less then 20):\n"); scanf("%d", &n); if (n >= 20) return 0; printf(" enter the integer array elements:\n" ); for(i = 0; i < n; i++) { scanf("%d", &a[i]); } // sort the loaded array, binary search! for(i = 0; i < n-1; i++) { for(j = 0; j < ni-1; j++) { if (a[j+1] < a[j]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } printf(" the sorted numbers are:"); for(i = 0; i < n; i++) { printf("%d ", a[i]); } // point to beginning and end of the array beg = &a[0]; end = &a[n]; // use n = one element past the loaded array! // mid should point somewhere in the middle of these addresses mid = beg += n/2; printf("\n enter the number to be searched:"); scanf("%d",&target); // binary search, there is an AND in the middle of while()!!! while((beg <= end) && (*mid != target)) { // is the target in lower or upper half? if (target < *mid) { end = mid - 1; // new end n = n/2; mid = beg += n/2; // new middle } else { beg = mid + 1; // new beginning n = n/2; mid = beg += n/2; // new middle } } // find the target? if (*mid == target) { printf("\n %d found!", target); } else { printf("\n %d not found!", target); } getchar(); // trap enter getchar(); // wait return 0; } 

Quelqu’un pourrait-il suggérer comment modifier ce programme ou un nouveau programme afin d’implémenter une recherche dynamic binary qui fonctionne comme expliqué ci-dessus !!

Ça sent les devoirs, car il existe généralement de meilleures méthodes pour mettre en œuvre la conception.

Permettez-moi de clarifier l’exigence: étant donné un tableau d’entiers contigus, ils peuvent être perçus comme étant dans l’ordre suivant:

 row 0: array[0] # row 1: array[1] # # row 2: array[3] # # # # row 3: array[7] # # # # # # # # 

L’algorithme de recherche, selon ma compréhension, est:

1. Recherche binary externe

Appliquez une recherche binary à la première “colonne”. Le résultat trouvera la ligne à rechercher.

2. Recherche binary en ligne

Appliquez une recherche binary à la ligne pour trouver la valeur exacte.

La recherche binary externe

L’étape suivante consiste à modifier un algorithme de recherche binary existant afin de faire progresser les indices “le plus bas” et “le plus élevé” en fonction de la disposition du tableau.

En regardant la mise en page ci-dessus, il semble y avoir un motif avec les indices de tableau pour chaque ligne. Ressemble à:

  [Equation 1] index = power(2, row #) - 1 

Dans une recherche binary, chaque itération choisit un point milieu, situé à mi-chemin entre le point le plus haut et le point le plus bas, normalement calculé comme suit:

 [Equation 2} midpoint = ((highest - lowest) / 2) + lowest 

Pour faciliter la compréhension, adoptons deux conventions d’indexation: index de lignes et index de colonnes . L’ index de ligne est le numéro de ligne, en fonction de la disposition. L’ index de la colonne sera la position dans la ligne. La mise en page ci-dessus contient 4 lignes. La rangée 2 a 4 colonnes.

Donc, pour trouver la ligne, nous utilisons la formule du point médian:

  row_midpoint = ((row_highest + row_lowest) / 2) + row_lowest 

Avant qu’une valeur puisse être comparée, elle doit être localisée en premier. L’emplacement est obtenu en branchant la valeur row_midpoint dans l’équation 1.

 array_midpoint_index = (1 << row_midpoint) - 1 

La valeur est ensuite obtenue en utilisant cet object array_midpoint_index : value = array [array_midpoint_index]

Pour éviter de répéter les calculs, je vous recommande d'enregistrer les valeurs, telles que row_low_value et row_high_value, à titre d'exemple.

Une fois que la ligne exacte est trouvée, il est temps de ...

Recherche binary en ligne

La recherche binary appliquée à la ligne est une recherche binary augmentée. L'augmentation détermine les indices de tableau des première et dernière colonnes de la ligne. Ces index de colonne peuvent être calculés en utilisant l'équation 1.

Les détails sont laissés comme un exercice pour le lecteur.
(En passant, faire des images et des diagrammes est toujours une pratique utile lorsque vous êtes bloqué sur un problème, que ce soit des algorithmes informatiques ou des problèmes de mots de physic.)

Maintenir la structure de données

La maintenance de cette structure de données, l'insertion et la suppression d'éléments, est plus facile à effectuer en la traitant comme un tableau unique. Une fois que l'index d'insertion est trouvé, déplacez les éléments vers le bas pour faire de la place pour un autre, puis insérez le nouvel élément.

Une meilleure structure de données

Une meilleure structure de données peut consister à avoir un tableau d'éléments [value, pointer, length] . Le pointeur indiquerait un autre tableau. Le champ longueur indique la longueur du tableau. Cela permet d’utiliser une recherche binary standard sur le champ de valeur. Une recherche binary standard peut être appliquée au tableau de lignes à l'aide des champs pointeur et longueur . La commodité réside dans le fait que les langages C et C ++ intègrent des fonctions de recherche binary standard, déjà testées, qui ne vous font pas perdre de temps à réécrire .

La recherche binary dynamic est vraiment un algorithme intéressant. La référence en est le problème 18-2 d’Introduction aux algorithmes (Cormen, Leiserson et Rivest) et est étroitement liée au fusionnement en ligne (Knuth TAOCP, ex 5.2.4-17). Il a O (log (n)) durée moyenne de la recherche réussie. Les recherches les plus défavorables avec succès et non avec succès sont toutes deux O (log 2 (n)). Et il est beaucoup plus facile de coder que les arbres de recherche équilibrés.

La recherche est assez simple, il vous suffit de rechercher chaque ligne jusqu’à ce que vous trouviez quelque chose (commencez par la plus grande). J’ai implémenté une insertion ci-dessous. La routine de fusion effectue tout le sorting. Notez que chaque ligne est un int * qui est identique à un tableau d’ints (ou NULL). Si je construisais une version haute performance, je chercherais à mettre en cache des baies de taille plus petite comme malloc et free ont tendance à être lentes.

 int *row[30]; int lastrow=0; void dbs_insert(int v); int *dbs_merge(int *a, int *b, int len); void dbs_insert(int v) { int *new_row; int i; new_row=malloc(sizeof(int)); new_row[0]=v; i=0; while (row[i]!=NULL) { new_row=dbs_merge(row[i],new_row,1<lastrow) lastrow=i; } int *dbs_merge(int *a, int *b, int len) { int ai=0; int bi=0; int ci=0; int *c; c=malloc((2*len)*sizeof(int)); while (ai