Incrémentation des instructions pour suivre les comparaisons dans la méthode récursive

Question

J'essaie de construire une méthode de recherche binaire récursive qui recherche un tableau trié d'objets comparables pour un objet d'intérêt. Cela fait partie d'un algorithme plus grand qui recherche une collection de tableaux triés et recherche les éléments communs à tous les tableaux de la collection. Le but est de rendre la partie recherche/comparaison de l'algorithme aussi efficace que possible. Une solution linéaire devrait être possible. Ceci est la méthode:

private static boolean BinarySearch(Comparable[] ToSearch, Comparable ToFind, int first, int last){ 
    boolean found = false; 
    int mid = first + (last - first)/2; 
    comparisons++; 
    if(first > last){ 
     found = false; 
    } 
    else if(ToFind.compareTo(ToSearch[mid]) == 0){ 
     found = true; 
     comparisons++; 
    } 
    else if(ToFind.compareTo(ToSearch[mid]) < 0) { 
     found = BinarySearch(ToSearch, ToFind, first, mid - 1); 
     comparisons++; 
    } 
    else{ 
     found = BinarySearch(ToSearch, ToFind,mid + 1, last); 
     comparisons++; 
    } 
    return found; 
} 

Le problème que j'ai suivi est le nombre de comparaisons par la récursivité. Parce que je dois compter les comparaisons qui évaluent à false aussi bien que vrai, j'ai essayé de placer l'instruction incrementing de comparaison dans chaque instruction de sélection mais cela ne fonctionne pas parce que l'instruction n'est pas incrémentée si l'instruction évalue à false. Je ne peux pas non plus les placer entre les déclarations de sélection parce que cela me donnerait autre chose sans les erreurs. Je me demande si c'était une mauvaise idée d'utiliser la récursion pour la recherche, mais je veux croire que c'est possible. Toute aide serait appréciée.

Answer 1

Peut-être que vous pourriez définir une variable dans chaque bloc if avec le nombre de comparaisons qu'il a fallu pour y arriver, et l'ajouter à la fin?

private static boolean BinarySearch(Comparable[] ToSearch, Comparable ToFind, int first, int last){ 
    boolean found = false; 
    int newComparisons = 0; 
    int mid = first + (last - first)/2; 
    if(first > last){ 
     found = false; 
     newComparisons = 1; 
    } 
    else if(ToFind.compareTo(ToSearch[mid]) == 0){ 
     found = true; 
     newComparisons = 2; 
    } 
    else if(ToFind.compareTo(ToSearch[mid]) < 0) { 
     found = BinarySearch(ToSearch, ToFind, first, mid - 1); 
     newComparisons = 3; 
    } 
    else{ 
     found = BinarySearch(ToSearch, ToFind,mid + 1, last); 
     newComparisons = 3; 
    } 
    comparisons += newComparisons; 
    return found; 
}