Gleiche binäre Suche funktioniert nicht, ein Umstand, aber in einem anderen

Question

Durch CS50, Pset3 und verzweifelt nach Hilfe/Geduld. Ich versuche umgesetzt helpers.c so dass find.c die richtigen Funktionen .. aufrufen hat es jedoch verbindet nicht ..

habe ich ein separates Stück, das ich testBinSearch betitelt und das tat Arbeit. Mit dem gleichen Code .. kann mir jemand sagen, warum ..? Hier

/** 
* 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); 

      } 
} 

ist der find.c Code:

/** 
* 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; 
    } 

} 

Und schließlich, hier ist der Code, gearbeitet (oder zumindest scheint es zu funktionieren) getrennt, wenn ich sie alle in einer Datei eingegeben ... betitelte testBinSearch unter

#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; 
} 

Kann mir jemand helfen und mir sagen, wo ich schief gelaufen? Ich kam mit dem Code und kopierte es direkt über, aber einer arbeitete (testBinSearch) und einer tat nicht (helpers.c) ..?

Answer 1

Ich bin mir nicht sicher, ob dies das ganze Problem deckt aber trotzdem ...

Diese Berechnung

midPoint = endPoint/2; 

falsch ist.

Angenommen, Sie haben ein Array von 100 Elementen. Der Code kann Sie in eine Situation bringen, in der Sie den Index 75 bis 99 mit dem Mittelpunkt dazwischen (z. B. 87) betrachten, d. H. Sie haben den Pfad smaller than ein paar Mal genommen.

Wenn man nun die greater than teilnehmen Sie einen Mittelpunkt (zum Beispiel 43) berechnen außerhalb des Bereichs von Interesse zu sein

Ferner ist der Startpunkt variabel keine Variable innerhalb des smaller than Fall zu sein. Es muss auf der gleichen Ebene wie der Endpunkt sein. In jeder Schleife müssen Sie entweder den Startpunkt oder Endpunkt ändern. Die Berechnung des Mittelpunkts hängt immer von Anfangs- und Endpunkt ab.