Est-il possible de n'avoir qu'une seule comparaison par itération d'un algorithme de recherche binaire?

Question

Dans l'algorithme de recherche binaire, nous avons deux comparaisons:

if (key == a[mid]) then found; 

else if (key < a[mid]) then binary_search(a[],left,mid-1); 
     else binary_search(a[],mid+1,right); 

est-il un moyen par lequel je ne peux avoir qu'une seule comparaison au lieu des deux ci-dessus.

-

Merci

Alok.Kr.

Answer 1

Voir:

http://en.wikipedia.org/wiki/Binary_search_algorithm#Single_comparison_per_iteration

Taken du wiki:

low = 0 
    high = N 
    while (low < high) { 
     mid = low + ((high - low)/2) 
     if (A[mid] < value) 
      low = mid + 1; 
     else 
      //can't be high = mid-1: here A[mid] >= value, 
      //so high can't be < mid if A[mid] == value 
      high = mid; 
    } 
    // high == low, using high or low depends on taste 
    if ((low < N) && (A[low] == value)) 
     return low // found 
    else 
     return -1 // not found 

Avantages/inconvénients de wiki: « Cette approche renonce à la possibilité de résiliation anticipée de la découverte d'un match, ainsi les recherches réussies ont des itérations de log2 (N) au lieu d'itérations de log2 (N) - 1. En revanche, cette implémentation fait moins de comparaisons: log2 (N) est le ss que le nombre attendu de comparaisons pour les implémentations de deux tests de 1. 5 (log2 (N) - 1), pour N supérieur à huit. "

Answer 2

Cet algorithme est récursif. La première comparaison est le critère d'arrêt et la deuxième recherche réelle, vous ne pouvez donc pas les supprimer.

En premier vous demandez à chaque fois que vous avez déjà trouvé l'élément et en second dans quelle partie du tableau rechercher élément. Vous ne pouvez donc pas prendre ces décisions uniquement sur la base d'une comparaison.

Answer 3

Oui. Il ne suffit pas d'éliminer mid de l'appel récursif.

if (left == right) return NULL; 
if (left + 1 == right) return key == a[left]? &a[left] : NULL; 

mid = left + (right - left/2); 

if (key < a[mid]) return binary_search(a[],left,mid-1); 
else return binary_search(a[],mid,right); // include `mid` in next round 

Vous avez seulement besoin d'éliminer la moitié de l'ensemble à chaque récursion pour obtenir une performance O (logN). Vous allez au-delà en éliminant la moitié + 1.

Si vous n'utilisez que < pendant la récursion, l'algorithme trouvera le moins élément qui n'est pas moins de key (mais peut être supérieur à key). Terminez en effectuant un test d'égalité unique.

Answer 4

En assembleur, vous pouvez:

cmp key,a[mid] 
beq found 
bge else 

Donc, si votre compilateur est vraiment bon à l'optimisation des judas, il pourrait déjà le faire pour vous.

Answer 5

Tout d'abord: avez-vous besoin d'optimiser le programme? Avez-vous mesuré pour savoir où vous devez le faire? Est-ce dans cette fonction?

Pour les types primitifs, la seconde comparaison est une opération aussi rapide que possible. Le coût plus élevé de la comparaison charge l'élément dans le registre approprié, ce qui est nécessaire pour la première comparaison. Une fois cette comparaison exécutée, la valeur est déjà dans un registre et la seconde opération prend une instruction de processeur unique plus le coût possible de l'erreur de branchement.

En supposant des types entiers, le coût en temps de processeur de l'algorithme est très probablement dominé par le coût des appels récursifs si le compilateur n'est pas capable d'effectuer une optimisation de récurrence de queue. Si vous avez vraiment besoin d'optimiser cela, essayez de compiler avec tous les indicateurs d'optimisation et analysez l'assembleur pour déterminer si l'optimisation tail-récursion est appliquée. Sinon, convertissez manuellement l'algorithme de récursif en itératif.

Cela aura deux effets: obscurcir le code (évitez de modifier une solution propre sauf si vous en avez vraiment besoin) et éviter les appels de fonction.

Si vous parlez de C++ et le type est complexe et les opérateurs de comparaison surchargées sont chers, le plus rapide coup de pouce de la performance met en œuvre une méthode compare qui renverra un nombre négatif pour moins que, 0 pour l'égalité et un nombre positif si supérieur à. Ensuite, précalculez le résultat avant les comparaisons, puis effectuez des vérifications sur les entiers uniquement. Cela va supprimer le coût global de l'algorithme à un seul traitement des objets réels avec la comparaison coûteuse et vous remettre dans l'hypothèse originale.

Answer 6

for (step = 0; step < n; step <<= 1); 

for (i = 0; step; step >>= 1) 
    if (i + step < n && v[i + step] <= x) 
     i += step; 

Answer 7

Ok, c'était une question d'entrevue dans Adobe, et j'essayais juste de comprendre comment faire ceci.

Maintenant, j'ai solution a à, donc, m affichage

void binary_search (int a[] , int low , int high , int key) 
{ 
    int mid = (low+high)/2; 

    if (key == a[mid]) { 
     printf ("Number Found\n"); 
     return; 
    } 

    else { 
     int sign = Calc_sign (key-a[mid]); 
     low = low*sign + (1-sign)*mid; 
     high = mid*sign + (1-sign)*right; 
     binary_search (a,low,high,key); 
    } 
} 

int Calc_sign(int a) 
{ 
    return ((a & 80000000) >> 31); 
} 

Ainsi, dans le code, il n'y aura une comparaison pour vérifier si le keyvalue est eqaul à l'élément mi.

-

Merci

Alok Kr.