Pourquoi mon implémentation de recherche binaire ne trouve-t-elle pas le dernier élément?

Question

J'ai implémenté une version récursive de début de recherche binaire en C. Cependant, cela ne semble pas fonctionner lorsque l'élément à trouver se trouve dans la dernière position du tableau. Est-il possible de résoudre ce problème sans changer le prototype de la fonction?

#include <stdio.h> 

int search(int value, int values[], int n); 

int main() { 
    int a[] = { 26, 27, 28 }; 

    if (search(28, a, 3) == 0) 
     printf("Found.\n"); 
    else 
     printf("Not found.\n"); 
} 

int search(int value, int values[], int n) 
{ 
    if (n <= 0) 
     return 1; 

    if (value < values[n/2]) 
     // Search the left half 
     return search(value, values, n/2); 
    else if (value > values[n/2]) 
     // Search the right half, excluding the middle term 
     return search(value, values + n/2 + 1, n/2 - 1); 
    else 
     return 0; 

    return 1; 
} 

Answer 1

Votre fonction search est incorrecte:

• La taille de la tranche que vous passez quand vous RECURSE sur la partie droite est calculée de manière incorrecte: il se doit être n - n/2 - 1 au lieu de n/2 - 1.

Voici une version corrigée:

#include <stdio.h> 

int search(int value, int values[], int n); 

int main(void) { 
    int a[] = { 26, 27, 28 }; 

    if (search(28, a, 3) == 0) 
     printf("Found.\n"); 
    else 
     printf("Not found.\n"); 

    return 0; 
} 

int search(int value, int values[], int n) { 
    if (n > 0) { 
     int mid = n/2; 
     if (value < values[mid]) { 
      // Search the left half 
      return search(value, values, mid); 
     } else 
     if (value > values[mid]) { 
      // Search the right half, excluding the middle term 
      return search(value, values + mid + 1, n - mid - 1); 
     } else { 
      // Found the value 
      return 0; 
     } 
    } 
    return 1; 
} 

Voici une version itérative simple:

int search(int value, int values[], int n) { 
    while (n > 0) { 
     int mid = n/2; 
     if (value < values[mid]) { 
      // Search the left half 
      n = mid; 
     } else 
     if (value > values[mid]) { 
      // Search the right half, excluding the middle term 
      values += mid + 1; 
      n -= mid + 1; 
     } else { 
      // Found the value 
      return 0; 
     } 
    } 
    return 1; 
} 

Answer 2

Il semble que ce soit votre déclaration de retour dans votre else if clause. La longueur du tableau n doit être n-n/2-1 et non n/2-1 sinon le dernier élément sera tronqué. Vous pouvez voir ceci pour être plus répandu pendant que la longueur du tableau augmente et pendant que vous recherchez des éléments venant du côté droit.

return search(value, values + n/2 + 1, n - n/2 - 1); 

Note: Comme chqrlie a souligné