二进制搜索没有返回正确的值

我正在C++中实现二进制搜索算法，但算法没有返回正确的值。代码可以找到here。二进制搜索没有返回正确的值

template<class T> 
int binary_search(T search_value, T search_array[]) { 

    int mid; /* The middle element of the remaining array to be searched. */ 
    int min = 0; /* The first index of the array. */ 
    /* This forumla gives us the size of the array. */ 
    int max = sizeof(search_array)/sizeof(search_array[0]); 

    /* Continue searching until min >= max. */ 
    while (min < max) { 
     /* Compute the value of mid using a formula that won't produce a number 
     * larger than the maximum allowed value of an integer. */ 
     mid = (max-min)/2 + min; 

     /* Depending the whether search_value is larger or smaller than the 
     * value of whatever is at search_array[mid], set one of mid and max 
     * equal to mid. */ 
     if (search_value > search_array[mid]) 
      min = mid + 1; 
     else if (search_value < search_array[mid]) 
      max = mid + 1; 
     else { 
      return mid; 
     } 
    } 

    return -1; 
}

鉴于数组{0，1，3，5，7，9}和搜索3，函数应返回2，3阵列中的索引。我的函数返回-1，这意味着3在数组中找不到。问题在哪里？

来源

2012-02-13 mau5padd

开始似乎是一个非常琐碎测试用例在调试器到步骤通过.. – Blorgbeard 2012-02-13 21:59:03

第一。在函数中使用sizeof-construction来接收数组大小是一个坏主意。在函数中再加一个参数，比如'int array_size' – mikithskegg 2012-02-13 22:00:57

你试过调试吗？ – littleadv 2012-02-13 22:01:27

int max = sizeof(search_array)/sizeof(search_array[0]);

这种方法不适合计算数组的大小，它只适用于创建数组的函数。

将数组大小作为函数的参数传递，这是最简单的方法。

来源

2012-02-13 21:58:28 Saphrosit

这工作。只是为了笑笑，有什么更好的方法来计算一个数组的大小？实质上，我所做的只是将'sizeof（search_array）/ sizeof（search_array [0]）'移到'main'方法并将其传递给函数。 – mau5padd 2012-02-13 22:06:38

问题是你的函数中的'search_array'只是一个指向内存地址的指针，而不是一个数组，因此这种方法在你创建数组的函数（在这种情况下，主要）除外。没有一种标准的方法来计算数组的大小，但是一种常见的方法是将其作为函数的参数传递。其他方法可能包括使用特定的结构，比如'std :: vector'，它存储数组的长度并消除在运行时计算它的问题。 – Saphrosit 2012-02-13 22:10:53

有一个在您的实现中的错误：

else if (search_value < search_array[mid]) 
    max = mid + 1;

应该是：

max = mid - 1;

来源

2012-02-13 21:58:32

虽然有一个错误，但这只会降低性能，而不是故障的原因，对吗？ – orlp 2012-02-13 22:01:10

可能不是。除非数组很小，否则它可能会访问超出数组范围的内存。 – 2012-02-13 22:01:51

我没看到这个，谢谢指出！ – mau5padd 2012-02-13 22:08:05

这条线是至少一个问题：

int max = sizeof(search_array)/sizeof(search_array[0]);

数组不通过传递功能，所以你的声明：

int binary_search(T search_value, T search_array[])

...是一样的：

int binary_search(T search_value, T *search_array)

就这样max是指针由元素的大小划分的大小，因此，在最好的情况下也可能是多达6个，但大多数可能是0或1

我想在C++中，你可以通过引用传递数组和使用知道声明的形式，这样它的大小：

template <size_t array_length> 
void foo (const char (&data) [array_length]) 
{ 
    // ... 
}

来源

2012-02-13 21:59:12

此行不会做你认为它母鹿S：

int max = sizeof(search_array)/sizeof(search_array[0]);

因为数组时，传递给函数的自动衰减的指针，这将有效地等于这个：

int max = sizeof(void*)/sizeof(search_array[0]);

这是不是你想要的。请使用std::vector，其中存储了您的大小或手动size_t array_length参数。

来源

2012-02-13 21:59:18 orlp

int max = sizeof(search_array)/sizeof(search_array[0]);

search_array是一个指针而不是数组。

函数原型中的参数类型为T的数组会自动调整为指向T的指针。

来源

2012-02-13 21:59:55 ouah

这条线是关于：

int max = sizeof(search_array)/sizeof(search_array[0]);

sizeof(search_array)将是一个指针的大小，4首或8个字节取决于平台。通常，我尽量避免在变量上使用sizeof。它在类型上使用更好。例如，你的情况sizeof(T)。

来源

2012-02-13 22:00:32

你的最大值需要是少一个作为索引从0

来源

2012-02-13 22:00:56 e7mac

二进制搜索没有返回正确的值

回答

相关问题