Recherche binaire en C avec fonction récursive n'acceptant que la longueur

Question

Je suis en train de résoudre des "Perles de programmation". 4.11 disent:

Ecrire et prouver l'exactitude d'une fonction de recherche binaire récursive en C ou C++ avec cette déclaration:

int binarySearch (DataType x [], int n);

Utilisez cette fonction uniquement; n'appelle pas toute autre fonction récursive.

je suis venu avec:

int bsearch_rec_array_only(int key, int* arr, int n) 
{ 
    int mid; 

    if (n < 0) 
     return -1; 

    mid = n/2; 

    if (arr[mid] == key) 
     return (int) ((size_t) arr + mid * sizeof(*arr)); 
    else if (arr[mid] < key) 
     return bsearch_rec_array_only(key, arr + mid + 1, n - mid - 1); 
    else 
     return bsearch_rec_array_only(key, arr, mid - 1); 
} 

Cependant - il y a un problème. Je retourne le décalage y compris l'adresse du tableau car sinon comment connaître le décalage relatif de l'élément au tableau d'origine?

Je besoin de cette enveloppe:

int bsearch_array_only_wrap(int key, int* arr, int n) 
{ 
    int offset; 
    if (n == 0) 
     return -1; 

    offset = bsearch_rec_array_only(key, arr, n); 

    if (offset == -1) 
     return -1; 
    else  
     return (offset - (int) arr)/sizeof(*arr); 
} 

Ce n'est pas récursive - il appelle simplement bsearch_rec_array_only et calcule le décalage.

Mais cela semble compliqué. Pouvez-vous trouver une meilleure solution?

Answer 1

Votre problème est que le code ne renvoie pas le décalage de l'élément du début du tableau, mais un pointeur converti en un int. Le fait que vous ayez utilisé un casting devrait vous montrer qu'il y a quelque chose qui ne va pas dans le code.

Essayez de renvoyer un décalage. Quelque chose comme ceci:

if (arr[mid] == key) 
     return mid; 
else if (arr[mid] < key) { 
     int i = bsearch_rec_array_only(key, arr + mid + 1, n - mid - 1); 
     return (i != -1) ? i + mid + 1 : -1; 
} else 
     return bsearch_rec_array_only(key, arr, mid - 1); 

Answer 2

Voici la réponse:

// Recursive binary search 
int bsearch(int key, int * arr, int n) 
{ 
    if (n == 0) 
    { 
     return -1; 
    } 

    int m = n/2; 
    int found; 

    if (arr[m] == key) 
    { 
     found = m; 
    } 
    else if (arr[m] < key) 
    { 
     // Upper half. We'll search in upper half of the current array with new length 
     // of the upper half. 
     found = bsearch(key, arr + m + 1, n - m - 1); 

     if (found != -1) 
     { 
      // Since we've found a key, need to offset it to make valid in the 
      // current search scope 
      found += m + 1; 
     } 
    } 
    else 
    { 
     // Lower half, there is no need to offset the array. 
     // New array length is equal to the current middle point. 
     found = bsearch(key, arr, m); 
    } 

    assert(found == -1 || (found >= 0 && found < n && arr[found] == key)); 

    return found; 
}