Тот же двоичный поиск не работает, одно обстоятельство, но работает в другом

Question

Переход через CS50, Pset3 и отчаяние за помощь/терпение. Я пытаюсь реализованным helpers.c так, что find.c имеет правильные функции для вызова .. Однако он не подключен ..

я сделал отдельную часть I под названием testBinSearch и сделал работу. С тем же кодом .. может кто-нибудь сказать мне, почему ...?

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

      } 
} 

Вот 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; 
    } 

} 

И, наконец, вот код, который работал (или, по крайней мере, кажется, работает) отдельно, когда я ключом их все в одном файле ... под названием testBinSearch ниже

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

Может кто-то помочь мне и скажите мне, где я пошло не так? Я придумал код и скопировал его прямо, но один работал (testBinSearch), а один не сделал (helpers.c) ..?

Answer 1

Я не уверен, если это покрывает всю проблему, но все равно ...

Этот расчет

midPoint = endPoint/2; 

неправильно.

Предположим, у вас есть массив из 100 элементов. Код может привести вас к ситуации, когда вы смотрите на индекс от 75 до 99 с промежуточной точкой между ними (например, 87), т. Е. Несколько раз вы использовали путь smaller than.

Теперь, если вы берете greater than часть вы рассчитали среднюю точку (например, 43), находясь вне диапазона интересов

Далее, переменная кузницы кадров не должна быть переменной внутри smaller than случае. Он должен быть на том же уровне, что и конечная точка. В каждом цикле вы должны изменить либо начальную точку , либо конечной точки. Расчет средней точки всегда зависит от начальной точки и конечной точки.