同样的二进制搜索在一种情况下不起作用，但在另一种情况下有效
Same Binary search not working, one circumstance, but working in another
经历 CS50、Pset3 并绝望 help/patience。
我正在尝试实施 helpers.c 以便 find.c 具有正确的函数来调用..但是它没有连接..
我做了一个名为 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）.. ?
我不确定这是否涵盖了整个问题，但无论如何...
这个计算
midPoint = endPoint/2;
错了。
假设您有一个包含 100 个元素的数组。该代码可能会让您看到索引 75 到 99 之间的中点（例如 87），即您已经走了几次 smaller than 路径。
现在，如果您采用 greater than 部分，您计算的中点（例如 43）超出了感兴趣的范围
此外，起点变量不是smaller than情况下的变量。它必须与端点处于同一级别。在每个循环中，您必须更改起点 或 终点。中点的计算应始终取决于起点和终点。
经历 CS50、Pset3 并绝望 help/patience。
我正在尝试实施 helpers.c 以便 find.c 具有正确的函数来调用..但是它没有连接..
我做了一个名为 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）.. ?
我不确定这是否涵盖了整个问题，但无论如何...
这个计算
midPoint = endPoint/2;
错了。
假设您有一个包含 100 个元素的数组。该代码可能会让您看到索引 75 到 99 之间的中点（例如 87），即您已经走了几次 smaller than 路径。
现在，如果您采用 greater than 部分，您计算的中点（例如 43）超出了感兴趣的范围
此外，起点变量不是smaller than情况下的变量。它必须与端点处于同一级别。在每个循环中，您必须更改起点 或 终点。中点的计算应始终取决于起点和终点。