Problème avec la fonction de recherche binaire

Question

Quelle que soit la valeur que je recherche, le programme indique qu'il n'est pas trouvé dans le fichier. Je ne peux pas comprendre ce qui ne va pas avec mon code.

 int main() 
    { 
     int array1[MAX_NUMBER]; 
     int length; 
     int number; 
     int location; 

     input (array1, MAX_NUMBER, length); 

     cout<<"Please enter a number to search for:"<<endl; 
     cin>>number; 

     location=search(array1, length, number); 

     if (location!=-1) 
     { 
      cout<<"The number "<<number<<" was found in the "<<location<<" position."<<endl; 
     } 

     else 
     { 
      cout<<"The number "<<number<<" was not found in the file."<<endl; 
     } 




     return 0; 
    } 

void input(int a[], int size, int& number_used) 
{ 
    ifstream infile; 
    int input; 

    infile.open("numbers.txt"); 

    if (infile.fail()) 
    { 
     cout<<"Input file opening failed."<<endl; 
     exit(1); 
    } 

    int i; 


    for (i=0; i<=size; i++) 
    { 
     while (infile>>input) 
     { 

      a[i]=input; 
      cout<<a[i]<<endl; 

     } 
    } 

    number_used=i; 

} 

int search(const int a[], int number_used, int search_value) 
{ 
    int start=1; 
    int end=number_used; 
    int key=search_value; 

    while (start<=end) 
    { 
     int mid=((start+end)/2); 

     if (a[mid]==key) 
     { 
      return mid; 
     } 

     if (a[mid]>key) 
     { 
      end=mid-1; 
     } 

     else 
     { 
      start=mid+1; 
     } 

    } 
     return -1; 


} 

Mon problème est-il dans le code principal ou dans la fonction de recherche?

fichier d'entrée:

1 
5 
6 
7 
11 
19 
21 
23 
33 
54 
78 
97 

Par exemple, en tapant 19, la sortie est "Le numéro 19 n'a pas été trouvé dans le fichier."

Answer 1

Les recherches binaires nécessitent que le tableau soit déjà trié. Essayez votre algorithme à la main: trouvez le numéro 4 dans [4, 1, 3, 6, 5]. 4 est supérieur à l'élément du milieu, donc l'algorithme ira à la partie [4, 6, 5] du tableau.

Answer 2

Vous ne calculez pas la longueur de la liste de valeurs correctement lues. Vous avez une boucle à l'intérieur d'une boucle, et ça fait quelque chose de bizarre.

Ce que vous devez faire est quelque chose comme:

int i; 

while (i < size && infile >> input) 
{ 
    a[i]=input; 
    cout<<a[i]<<endl; 
    i++; 
} 

number_used=i; 

Answer 3

Vous n'êtes pas remplir le tableau correct dans la fonction input. Vous devez utiliser un autre indice pour stocker des valeurs dans le tableau, sinon i n'indique pas un indice valable et significatif dans a:

int k = 0; // <-------------------------- 

int i; 
for (i = 0; i <= size; i++) 
{ 
    while (infile >> input && k < size) 
    { 

     a[k] = input; // <---------------- 

     k++; // <---------------- 
    } 
} 

number_used = k; // <------------- 

Et, comme WhozCraig a commenté, vous devez savoir les tableaux commencent à partir 0 ne 1 donc search méthode:

int start = 0;