如果语句不识别真实条件？

Question

我在使用这个二进制搜索算法时遇到了问题。以下是对变量的解释。

value: 在数组中搜索的数字

values[]: 正在搜索的数组

n: 数组中的元素个数

high：被搜索数组部分的最高元素（按零索引位置）

low：最低元素（按零索引位置）正在搜索的数组部分

我的问题不是递归。正在搜索的数组部分以 "value" 为中心，并且满足以下确定的条件。问题是我的 if 语句似乎没有意识到它们是。我知道条件得到满足，因为当我为每个递归打印出值[高]、值[中]和值[低]时，它表明它们是。

int search(int value, int values[], int n, int high, int low)
 {   
   if (n <= 0)
   {
    return 1;
   }

   int middle = (high + low) / 2;

     ///condition #1
   if (value == values[middle])
   {
     return 0;
   }

   //conditions #2 and #3 (account for the maxes and mins of the array because the operation to find middle truncates)
  else if ( values[middle]==values[low] || values[middle]==values[high])
    {
     return 0;
    }

  else if (value > values[middle])
   {
        low = middle;
        search(value, values, n, high, low);
   }

  else if (value < values[middle])
   {
      high = middle;
      search(value, values, n, high, low);
   }

    return 2;
   }

这是怎么回事？

Answer 1

仔细看这段代码：

else if (value > values[middle])
{
     low = middle;
     search(value, values, n, high, low);
}

else if (value < values[middle])
{
   high = middle;
   search(value, values, n, high, low);
}

请注意，在这些情况下，您会递归调用 search 函数，但不会对 return 值执行任何操作。这意味着 search 编辑的任何值都被丢弃，代码照常继续，最终 returning 2.

要解决此问题，请添加这些 return 语句：

else if (value > values[middle])
{
     low = middle;
     return search(value, values, n, high, low);
}

else if (value < values[middle])
{
   high = middle;
   return search(value, values, n, high, low);
}

一般来说，如果您怀疑 if 语句条件未触发，则值得使用调试器慢慢逐步完成。这样做可能会让您注意到您是 (1) 正确地递归调用函数，但 (2) returning 并丢弃 returned 值。

这里的代码可能还有其他问题，但这肯定是您需要解决的问题。

Answer 2

cb3k

That seemed to make it work...what might the other problems be?

这是您的代码，其中包含最少的（必要但不充分） diagnosed by templatetypedef 和测试工具。

#include <stdio.h>

static
int search(int value, int values[], int n, int high, int low)
{
    if (n <= 0)
    {
        return 1;
    }

    int middle = (high + low) / 2;

    ///condition #1
    if (value == values[middle])
    {
        return 0;
    }

    // conditions #2 and #3 (account for the maxes and mins of the array because the operation to find middle truncates)
    else if (values[middle] == values[low] || values[middle] == values[high])
    {
        return 0;
    }

    else if (value > values[middle])
    {
        low = middle;
        return search(value, values, n, high, low);
    }

    else if (value < values[middle])
    {
        high = middle;
        return search(value, values, n, high, low);
    }

    return 2;
}

int main(void)
{
    int data[15];
    for (int i = 0; i < 15; i++)
        data[i] = 2 * i + 1;

    printf("Data:");
    for (int i = 0; i < 15; i++)
        printf("%3d", data[i]);
    putchar('\n');

    for (int i = -1; i < 2 * 15 + 3; i++)
        printf("Search for %2d - result %d\n", i, search(i, data, 15, 14, 0));
    return 0;
}

这是输出：

Data:  1  3  5  7  9 11 13 15 17 19 21 23 25 27 29
Search for -1 - result 0
Search for  0 - result 0
Search for  1 - result 0
Search for  2 - result 0
Search for  3 - result 0
Search for  4 - result 0
Search for  5 - result 0
Search for  6 - result 0
Search for  7 - result 0
Search for  8 - result 0
Search for  9 - result 0
Search for 10 - result 0
Search for 11 - result 0
Search for 12 - result 0
Search for 13 - result 0
Search for 14 - result 0
Search for 15 - result 0
Search for 16 - result 0
Search for 17 - result 0
Search for 18 - result 0
Search for 19 - result 0
Search for 20 - result 0
Search for 21 - result 0
Search for 22 - result 0
Search for 23 - result 0
Search for 24 - result 0
Search for 25 - result 0
Search for 26 - result 0
Search for 27 - result 0
Search for 28 - result 0
Search for 29 - result 0
Search for 30 - result 0
Search for 31 - result 0
Search for 32 - result 0

无论查找的值是否存在于数组中，它都返回 0。这是不正确的行为。

你应该抽出时间学习 Jon Bentley 的 Programming Pearls。它涵盖了多种形式的二进制搜索测试的很多基础知识——显示的测试工具是他描述的变体。也花时间阅读额外，额外 - 阅读所有相关内容：几乎所有二进制搜索和合并排序都已损坏。也许你应该放心，随着时间的推移，很多其他人都把二分查找弄错了。（IIRC，二进制搜索的第一个版本发布于 1950 年代，但直到 1960 年代初才发布了正确的版本——然后还有 2006 年的 Extra 信息。）

当我在 else if (values[middle] == values[low] || values[middle] == values[high]) 之后的块中添加 printf() 时，它会在每个应该失败的搜索上打印出来。请注意，该界面很难发现正在发生的事情——它不报告元素在哪里找到，而只是报告是否找到了。您可以添加必要的调试和代码更改来处理残留问题。（提示：该条件可能不是解决方案的一部分。但是，当您删除它时，代码会进入永久循环，因为您没有消除已知不在递归检查范围内的值.)

这似乎有效——请注意 return 2; 永远不会执行（因为最后的 else if 永远不会为假。

#include <stdio.h>

static
int search(int value, int values[], int n, int high, int low)
{
    //if (n <= 0)
    if (n <= 0 || high < low)
    {
        return 1;
    }

    int middle = (high + low) / 2;

    ///condition #1
    if (value == values[middle])
    {
        return 0;
    }

#if 0
    // conditions #2 and #3 (account for the maxes and mins of the array because the operation to find middle truncates)
    else if (values[middle] == values[low] || values[middle] == values[high])
    {
        //printf(" (#2 || #3) ");
        return 0;
    }
#endif

    else if (value > values[middle])
    {
        //low = middle;
        low = middle + 1;
        return search(value, values, n, high, low);
    }

    else if (value < values[middle])
    {
        //high = middle;
        high = middle - 1;
        return search(value, values, n, high, low);
    }

    return 2;
}

int main(void)
{
    int data[15];
    for (int i = 0; i < 15; i++)
        data[i] = 2 * i + 1;

    printf("Data:");
    for (int i = 0; i < 15; i++)
        printf("%3d", data[i]);
    putchar('\n');

    for (int i = -1; i < 2 * 15 + 3; i++)
        printf("Search for %2d - result %d\n", i, search(i, data, 15, 14, 0));
    return 0;
}

输出：

Data:  1  3  5  7  9 11 13 15 17 19 21 23 25 27 29
Search for -1 - result 1
Search for  0 - result 1
Search for  1 - result 0
Search for  2 - result 1
Search for  3 - result 0
Search for  4 - result 1
Search for  5 - result 0
Search for  6 - result 1
Search for  7 - result 0
Search for  8 - result 1
Search for  9 - result 0
Search for 10 - result 1
Search for 11 - result 0
Search for 12 - result 1
Search for 13 - result 0
Search for 14 - result 1
Search for 15 - result 0
Search for 16 - result 1
Search for 17 - result 0
Search for 18 - result 1
Search for 19 - result 0
Search for 20 - result 1
Search for 21 - result 0
Search for 22 - result 1
Search for 23 - result 0
Search for 24 - result 1
Search for 25 - result 0
Search for 26 - result 1
Search for 27 - result 0
Search for 28 - result 1
Search for 29 - result 0
Search for 30 - result 1
Search for 31 - result 1
Search for 32 - result 1

如果语句不识别真实条件？

If statement not recognizing true conditions?

c

binary-search