c - 为什么我的二分查找在未找到元素时返回 "true"？

Question

查找.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;
    }
}

helpers.c

 /**
 * helpers.c
 *
 * Computer Science 50
 * Problem Set 3
 *
 * Helper functions for Problem Set 3.
 */

#include <cs50.h>

#include "helpers.h"

/**
 * Returns true if value is in array of n values, else false.
 */
bool search(int value, int values[], int n)
{
    int temp = values[n/2];
    do {
            if (temp == value)
            {
                return true;
            }
            else if (temp < value)
            {
               temp = temp + temp / 2;
            }
            else if (temp > value)
            {
              temp = temp - temp / 2;
            }
        } while(temp > 1);
    return false;   
}



/**    for (int i = 0; i < n; i++)
*    {
*       if (values[i] == value)
*        {
*            return true;
*        }
*    }
*    return false;
*}
*/
/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    int swaps = -1;
    do {
        swaps = 0;
        for(int i = 0, temp; i < n; i++)
        {
            if(values[i] > values[i+1])
            {
                temp = values[i+1];
                values[i+1] = values[i];
                values[i] = temp;
                swaps = swaps + 1;
            }
        }
    }while(swaps != 0);
    return;
}

我被难住了。搜索功能是helpers.c 文件中的功能。当我检查程序时，即使在数组中找不到该数字，它也会“返回 0”。我希望了解它为什么这样做。

Answer 1

您应该每次将values[temp]与value进行比较，而不是将temp与values进行比较。此外，您不应该给出值values[n/2]，而应该给出n/2，并且您的实现不涵盖该值是否为值[0]，因为你有条件 while(temp >1) 所以 temp 总是 >1 ，如果值是值[2](例如值[]={1,2, 3,4,5} ,值=5)。
所以你应该在最后添加:

if (values[1]==value || values[0]==value ) return true;

最后，如果值大于值 temp 的最大元素，它将不断增加，因此您将出现无限循环，因此我将条件更改为:

while(temp >1 && temp<n);

根据评论中的建议，您可以通过保留低、中和上限变量而不是仅使用 temp 来更好地编写搜索函数。

   bool search(int value, int values[], int n)
{
    int temp = n/2;
    do {
            if (values[temp] == value)
            {
                return true;
            }
            else if (values[temp] < value)
            {
               temp = temp + temp/ 2;
            }
            else if (values[temp] > value)
            {
              temp = temp /2; //temp-temp/2 equals to temp/2
            }
        } while(temp >1 && temp<n);
    if (values[1]==value || values[0]==value ) return true;
    return false;   
}