Même recherche binaire ne fonctionne pas, une circonstance, mais de travailler dans un autre

Question

En passant par CS50, Pset3 et désespérément besoin d'aide/patience. Je suis en train de helpers.c mis en œuvre pour que find.c a les fonctions correctes pour appeler .. Cependant, il ne se connecte pas ..

J'ai fait une pièce séparée, je testBinSearch et intitulé qui a fait le travail. Avec le même code .. quelqu'un peut-il me dire pourquoi ..?

/** 
* helpers.c 
* 
* Computer Science 50 
* Problem Set 3 
* 
* Helper functions for Problem Set 3. 
*/ 
#include <stdio.h>  
#include <cs50.h> 

#include "helpers.h" 

/** 
* Returns true if value is in array of n values, else false. 
*/ 
//search(needle, haystack, size) 
bool search(int value, int values[], int n) 

{ 
    // TODO: implement a Binary searching algorithm (You are welcome to take an iterative approach (as with a loop) or a recursive approach (wherein a function calls itself).) 



     //define startPoint. numberOfArrayElements(aka size) - (numberOfArrayElements(aka size) - 1) or Element[0] 

     //define endPoint. numberOfArrayElements(aka size) 
     int endPoint = n - 1; //element! we -1 because array start from 0th element. last element of array that is 5 elements big will thus be (total number of Elements - 1)th element. 

     //define midPoint. numberOfArrayElements(aka size)/2 
     int midPoint = endPoint/2; //element! 

     //while loop? 
     while(n > 0) 
      { 
       //if midPoint == needle, return 0 
       if(values[midPoint] == value) 
       { 
        return 0; 
       } 

       //////////(if midPoint is smaller(to the left) or larger(to the right) than needle) 
       //ELSE IF midPoint > than needle(look left), keep startPoint, change endPoint element to values[midPoint - 1], define midPoint again. 
       else if(values[midPoint] > value) 
       { 
        endPoint = midPoint - 1; 
        midPoint = endPoint/2; 
        n = endPoint; 
        printf("mid point is more than needle\n"); 
       } 
       //ELSE midPoint < than needle(look right), keep endPoint, change Startpoint element to values[midPoint + 1], define mindPoint again. 
       else if(values[midPoint] < value) 
       { 
        int startPoint = midPoint + 1; 

        //define midpoint again 
        midPoint = (endPoint + startPoint)/2; 
        n = endPoint - startPoint + 1; 
        printf("mid point is less than needle\n"); 
       } 


      } 



     printf("cued the while loop return 1\n"); 
     return 1; 
} 

/** 
* Sorts array of n values. Done with Insertion sort* 
*/ 
void sort(int values[], int n) 
{ 
    //declare variable 
    int element; 

    //number of iterations (or passes?). Skip first because first array is already sorted 
    for (int i = 1; i < n; i++) 
     { 
      //value of element moving into sorted portion 
      element = values[i]; 

      //declare variable 
      int j = 0; 

      //index into the unsorted portion 
      j = i; 

      //iterate sorted portion from right to left while sorted portion is greater than 'Element' being compared in this iteration of i. 
      //basically, it stops this loop once the 'Element' is placed to the left of all greater&&sorted numbers. 
      while(j > 0 && values[j - 1] > element) 
      { 
       //shift all sorted positions to the right 
       values[j] = values[j - 1]; 

       // this enables the loop to move left through the sorted portion 
       j = j - 1; 

      } 

      //insert temp holder value into the position which is now empty because all sorted&&greater number are to the right of 'Element' 
      values[j] = element; 

     } 


     for(int k = 0; k < n; k++) 
     //print to check 
      { 
       printf("{%i}<-- number in %i-th array (sorted)\n", values[k], k); 

      } 
} 

Voici le code find.c:

/** 
* find.c 
* 
* Computer Science 50 
* Problem Set 3 
* 
* Prompts user for as many as MAX values until EOF is reached, 
* then proceeds to search that "haystack" of values for given needle. 
* 
* Usage: ./find needle 
* 
* where needle is the value to find in a haystack of values 
*/ 

#include <cs50.h> 
#include <stdio.h> 
#include <stdlib.h> 

#include "helpers.h" 

// maximum amount of hay 
const int MAX = 65536; 

int main(int argc, string argv[]) 
{ 
    // ensure proper usage 
    if (argc != 2) 
    { 
     printf("Usage: ./find needle\n"); 
     return -1; 
    } 

    // remember needle 
    int needle = atoi(argv[1]); 

    // fill haystack 
    int size; 
    int haystack[MAX]; 
    for (size = 0; size < MAX; size++) 
    { 
     // wait for hay until EOF 
     printf("\nhaystack[%i] = ", size); 
     int straw = GetInt(); 
     if (straw == INT_MAX) 
     { 
      break; 
     } 

     // add hay to stack 
     haystack[size] = straw; 
    } 
    printf("\n"); 

    // sort the haystack 
    sort(haystack, size); 

    // try to find needle in haystack 
    if (search(needle, haystack, size)) 
    { 
     printf("\nFound needle in haystack!\n\n"); 
     return 0; 
    } 
    else 
    { 
     printf("\nDidn't find needle in haystack.\n\n"); 
     return 1; 
    } 

} 

Et enfin, voici le code qui a fonctionné (ou au moins il semble fonctionner) séparément quand je les ai tous KeyEd dans un fichier intitulé ... testBinSearch ci-dessous

#include <stdio.h> 
#include <cs50.h> 

void sort(int array[], int NumberOfElements); 
bool search(int value, int values[], int n); 

int main(void) 


{ 
    //decalre variable 
    int NumberOfElements; 

    printf("how many Element would you like in this array?\n"); 
    NumberOfElements = GetInt(); 

    //declare variable for array 
    int array[NumberOfElements]; 


    for(int i = 0; i < NumberOfElements; i++) 
     { 
      printf("alright, please key in value of each element\n"); 
      array[i] = GetInt(); 
     } 

    sort(array, NumberOfElements); 

    for (int i = 0; i < NumberOfElements; i++) 
     { 
      printf("alright, here is your array sorted, element %i is %i\n", i, array[i]); 
     } 

    printf("value ot search for?\n"); 
    int value = GetInt(); 
    search(value, array, NumberOfElements); 
} 


//---------- 
void sort(int array[], int NumberOfElements) 
{ 
    //declare variable 
    int element; 

    //number of iterations (or passes?). Skip first because first array is already sorted 
    for (int i = 1; i < NumberOfElements; i++) 
     { 
      //value of element moving into sorted portion 
      element = array[i]; 

      //declare variable 
      int j = 0; 

      //index into the unsorted portion 
      j = i; 

      //iterate sorted portion from right to left while sorted portion is greater than 'Element' being compared in this iteration of i. 
      //basically, it stops this loop once the 'Element' is placed to the left of all greater&&sorted numbers. 
      while(j > 0 && array[j - 1] > element) 
      { 
       //shift all sorted positions to the right 
       array[j] = array [j - 1]; 

       // this enables the loop to move left through the sorted portion 
       j = j - 1; 

      } 

      //insert temp holder value into the position which is now empty because all sorted&&greater number are to the right of 'Element' 
      array[j] = element; 

     } 

} 

//-------------- 
bool search(int value, int values[], int n) 

{ 
    // TODO: implement a Binary searching algorithm (You are welcome to take an iterative approach (as with a loop) or a recursive approach (wherein a function calls itself).) 

    //variables declaration 
    //int startPoint; 
    //int endPoint; 
    //int midPoint; 

     //define startPoint. numberOfArrayElements(aka size) - (numberOfArrayElements(aka size) - 1) or Element[0] 

     //define endPoint. numberOfArrayElements(aka size) 
     int endPoint = n - 1; //element! 

     //define midPoint. numberOfArrayElements(aka size)/2 
     int midPoint = endPoint/2; //element! 

     //while loop? 
     while(n > 0) 
      { 
       //if midPoint == needle, return 0 
       if(values[midPoint] == value) 
       { 
        printf("found it!\n"); 
        return 0; 
       } 

       //////////(if midPoint is smaller(to the left) or larger(to the right) than needle) 
       //ELSE IF midPoint > than needle(look left), keep startPoint, change endPoint element to values[midPoint - 1], define midPoint again. 
       else if(values[midPoint] > value) 
       { 
        endPoint = midPoint - 1; 
        midPoint = endPoint/2; 
        n = endPoint; 
       } 
       //ELSE midPoint < than needle(look right), keep endPoint, change Startpoint element to values[midPoint + 1], define mindPoint again. 
       else if(values[midPoint] < value) 
       { 
        int startPoint = midPoint + 1; 

        //define midpoint again 
        midPoint = (endPoint + startPoint)/2; 
        n = endPoint - startPoint + 1; 
       } 


      } 


     printf("could not find it\n"); 
     return 1; 
} 

que quelqu'un peut me aider et me dire où je suis allé mal? Je suis venu avec le code et l'ai copié juste au-dessus, mais on a travaillé (testBinSearch) et on n'a pas (helpers.c) ..?

Answer 1

Je ne suis pas sûr que cela couvre tout le problème, mais quand même ...

Ce calcul

midPoint = endPoint/2; 

est faux.

Supposons que vous avez un tableau de 100 éléments. Le code peut vous amener à une situation où vous regardez les index 75 à 99 avec un point médian entre (par exemple 87), c'est-à-dire que vous avez pris le chemin smaller than plusieurs fois.

Maintenant, si vous prenez la partie greater than vous calculer un point médian (par exemple 43) étant en dehors de la plage d'intérêt

En outre, la variable startpoint est de ne pas être une variable dans le cas smaller than. Il doit être au même niveau que le point de terminaison. Dans chaque boucle, vous devez modifier le point de terminaison ou. Le calcul du point médian doit toujours dépendre à la fois du point de départ et du point final.