Comment créer de nouveaux tableaux avec les valeurs max/min modifiées pour cette fonction de recherche binaire

Question

J'essaye d'implémenter une fonction de recherche binaire, je me demandais comment modifier les nouveaux tableaux avec de nouvelles valeurs min/max. Aussi, je suis nouveau en C++, donc quelqu'un peut-il me dire si c'est une implémentation correcte de la recherche binaire? Je vous remercie.

#include <iostream> 

using namespace std; 

bool doSearch(int arr, int target) 
{ 
int min = 0;  
int max = arr.length() - 1; 
while(min != max) 
{ 
    int avg = (min + max)/2;   
    if(arr[avg] < taget){ 
     min = avg + 1 
    } 
    else if(arr[avg] > target){ 
     max = avg - 1; 

    else if (arr[avg] == target) 
     { 
      return avg; 
     } 
    } 
} 
return -1; 

}

int main() 
{ 
int primes[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,61,67,71,73,79,83}; 
int result = doSearch(primes , 47); 
cout<<"Found prime at index " <<result; 

} 

Answer 1

bool doSearch

Si vous voulez retourner l'index, alors cela devrait être

int doSearch 

---

doSearch (int arr, cible int)

devrait plutôt être quelque chose comme

doSearch(int arr[], int size, int target) 

Parce que C++, il n'y a pas de fonction prédéfinie pour obtenir la longueur d'un tableau. Donc, votre fonction ressemblerait

int doSearch(int arr[], int size, int target)

---

while (min!= Max)

doit-elle être

while (min <= max) 

Parce que, sinon, la recherche ne renvoie l'index lorsque la cible est à l'index où min = max. c'est-à-dire, considérons le cas int arr[] = {0}; et l'appel de fonction doSearch(arr, 1, 0);.

---

Pour trouver la taille du tableau, vous pouvez utiliser

sizeof(primes)/sizeof(primes[0]) 

Ainsi, votre appel de fonction devient

int size = sizeof(primes)/sizeof(primes[0]); 
int result = doSearch(primes, size, 47); 

Prenez note que vous ne pouvez pas calculer la taille comme ci-dessus à l'intérieur la fonction doSearch, car les tableaux sont passés en tant que pointeurs vers la fonction.

---

De plus, une fois à l'intérieur if (arr[avg] < target) et else if (arr[avg] > target), il n'y a pas besoin de vérifier les conditions restantes, afin que vous puissiez utiliser continuer à passer à la prochaine itération de la boucle while-à-dire,

if (arr[avg] < target) 
{ 
    min = avg + 1; 
    continue; 
} 
else if (arr[avg] > target) 
{ 
    max = avg - 1; 
    continue; 
} 

---

Enfin, puisque votre principal attend un retour int, vous pouvez return 0 et avant de retourner utiliser system("pause"), de sorte que la fenêtre de la console ne se ferme pas dès qu'il affiche le résultat.

system("pause"); 
return 0; 

Answer 2

Vous devez apporter les modifications suivantes.

• Premier changement de type de retour de doSearch de bool à int.
• Ensuite, ajoutez ; dans requis des endroits tels que min = avg + 1;
• Changez en condition de boucle à while(min <= max)

• changer ensuite votre code principal() pour

  if(result != -1) cout<<"Found prime at index "<<result; else cout<<" Not found";

Answer 3

#include <iostream> 
using namespace std; 


template<size_t N> 
int doSearch(int(&arr)[N], int target) 
{ 
    int max = N - 1; 
    int min = 0; 
    int returnValue = -1; 


    while (min <= max) 
    { 
     int avg = (min + max)/2; 
     if (arr[avg] < target) { 
      min = avg + 1; 
     } 
     else if (arr[avg] > target) { 
      max = avg - 1; 
     } 
     else if (arr[avg] == target) 
     { 
      return avg; 
     } 

    } 
    return returnValue; 
} 


int main() 
{ 
    int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 }; 

    int result = doSearch(primes, 47); 
    cout << "Found prime at index " << result<<endl; 


    system("PAUSE"); 
    return 0; 
} 

Vous avez eu une poignée d'erreurs dans votre code - les deux syntaxe et logique. Votre première erreur a été le processus par lequel vous avez trouvé la longueur du tableau. J'ai utilisé un moyen pas si typique pour trouver la longueur - il y a d'autres façons de le faire mais je l'ai fait en utilisant des modèles parce que c'est plus amusant. Aussi dans votre boucle while vous l'avez eu while(min!=max) cela n'arrivera jamais à la réponse car il s'arrêterait si la réponse se trouve à une position où min et max sont les mêmes - par exemple votre tableau. Aussi votre fonction d'origine renvoyait un bool - cela n'a aucun sens puisque vous recherchez la position int. Il se peut qu'il y ait encore des erreurs dans ce code. N'hésitez pas à corriger. J'espère que ça aide!