Pourquoi ne pas utiliser la récursion pour la recherche binaire pour un tableau trié

Question

J'essaye d'implémenter une recherche binaire où n est la taille de mon tableau et ne fonctionne pas avec la récursivité, seulement quand je n'utilise pas la récursivité, ça marche, et je ne semble pas comprendre pourquoi

int mid = 0; 
int low = 0; 

bool search(int value, int values[], int n) 
{ 
    do 
    { 
    mid = (low + n)/2; 
    if(values[mid] == value) 
    { 
     return true; 
    } 
    else if (values[mid]>value) 
    { 
     n= mid -1; 
     return search(value, values, n); 


    } 
    else if (values[mid]<value) 
    { 
     low = mid + 1; 
     return search(value, values, low); 

    } 
} 
while (n > low); 

return false; 
} 

Answer 1

Votre programme est un mélange de deux solutions différentes. Vous devez soit résoudre celui-ci avec une boucle ou avec une fonction récursive.

La boucle que vous essayez d'utiliser devrait faire quelque chose comme ça. Aucune récursion nécessaire ici.

while (low <= high) { 
    mid = (low+high)/2; 
    if (value < values[mid]) 
     high = mid - 1; 
    else if (value > values[mid]) 
     low = mid + 1; 
    else 
     return true; 
} 
return false; 

Si vous avez besoin d'utiliser la récursivité, aucune boucle n'est nécessaire. votre réponse peut ressembler à ceci:

bool search(int value, int values[], int low, int high) { 
    if (low <= high) { 
     int mid = (low + high)/2; 
     if (values[mid] == value) 
     return true; 
     else if (value > values[mid]) 
     return search(value, values, mid+1, high); 
     else 
     return search(value, values, 1, mid-1); 
    } 
    return false; 
} 

Je suppose que vous pouvez définir ici votre propre en-tête de fonction.

Answer 2

Le problème est que vous appelez votre appel récursif pour rechercher la moitié supérieure du tableau avec un pointeur vers la moitié inférieure. Donc, si la valeur est dans la moitié supérieure, elle ne la trouvera pas. Vous avez besoin de quelque chose comme:

bool search(int value, int values[], int n) { 
    int mid = n/2; 
    if (n <= 0) { 
     return false; 
    } else if (values[mid] == value) { 
     return true; 
    } else if (values[mid] > value) { 
     return search(value, values, mid); 
    } else if (values[mid] < value) { 
     return search(value, values + mid + 1, n - mid - 1); 
    } 
}