我在我的 C 二进制搜索代码中做错了什么？（迭代和递归）

Question

我在这里做错了什么？原型是不可更改的。我需要编写这两个函数，这就是我写的。他们 90% 的时间都在工作。当我尝试搜索中间元素时，迭代方式出现问题。

递归方式出现了一些问题，但我真的不知道哪里出了问题。有时它会找到元素，有时找不到。

我无法更改的另一件事是我必须避免检查函数内部是否array[middle] == key。老师希望我们只在我退出循环时才做这个检查，他希望循环只检查我应该向右还是向左。

int *BinarySearchIter(const int SortedArray[], int key, size_t length)
{
    /*  variables that will set the boundries of the searched area      */
    int left_index = 0, right_index = 0, middle = 0;
    int *result = NULL;
    
    assert(SortedArray);
    assert(length);
    
    left_index = 0;             /*  first elemenet in the array         */
    right_index = length - 1;   /*  last elemenet in the  array         */

    /* while only one elemenet is left in the searched area             */
    while (left_index <= right_index)
    {
        /* split it to half                                             */
        middle = (left_index + right_index) / 2;
        
        /*  if key greater, ignore left half, search only in right half */
        if (SortedArray[middle] < key)
        {
            left_index = middle + 1;
        }
        /*  if key smaller, ignore right half, search only in left half */
        else
        {
            right_index = middle - 1;
        }
    }

    /*  if we reach here, then element is the key or was not found      */
    result = (int *)SortedArray + middle;
            
    return (key == *result ? result : NULL);
}
/******************************************************************************/
int *BinarySearchRec(const int SortedArray[], int key, size_t length)
{
    int left_index = 0; /*  first elemenet of the array */
    int right_index = length - 1; /* last elemenet in the array */  
    int middle = 0, isBigger = 0;
    
    if (1 == length)    
    {
        return (key == *SortedArray ? (int *)SortedArray : NULL);
    }
    
    middle = (left_index + right_index) / 2;    

    isBigger = (key > SortedArray[middle]);
    
    return (BinarySearchRec(SortedArray+(middle + 1)*isBigger, key, isBigger * (length - length /2 ) + !isBigger*(length/2)));
    
}
/******************************************************************************/

我正在尝试运行以下测试；

const int sorted_arr[] = { 2, 4, 8, 10, 12};
    
    size_t arr_length = sizeof(sorted_arr) / sizeof(sorted_arr[0]), i = 0;
    
    int key_to_find = 0;
    
    int *iterative_res = NULL;
    int *recursive_res = NULL;
    
    for (i = 0; i < arr_length; ++i)
    {
        key_to_find = sorted_arr[i];
        iterative_res = BinarySearchIter(sorted_arr, key_to_find, arr_length);
        recursive_res = BinarySearchRec(sorted_arr, key_to_find, arr_length);
        Print if any errors (nulls or key doesn't match any of the results)
    }

这是测试的输出：

ERRORS:

Needs to find: 8
But found:
Iterative: NULL (failure)
Recursive: NULL (failure)

Needs to find: 12
But found:
Iterative: 12 (success)
Recursive: NULL (failure)

Answer 1

对于迭代函数

让我们想想你的代码在做什么。您有一个包含 5 个元素的数组，假设您正在搜索 8.

2 4 8 10 12
    ^

在第一次迭代中，值是这样的：

left_index = 0, right_index = 4, middle_index = 2

在 if 语句中，程序检查 (SortedArray[middle_index] < key) 这是错误的，因为 8 不大于 8。所以它执行else 语句。错误就在这里。

在 else 语句中，您将丢弃中间元素。但在这种情况下，中间元素是您要查找的键。

因此，您需要更改的第一件事就像 @Eric Postpischil 所说的那样，将您的 else 语句更改为：

else {
  right_index = middle;
}

让我们继续第二次迭代：

2 4 8
  ^
left_index = 0, right_index = 2, middle_index = 1

第二次迭代后，第三次迭代将只包含 1 个元素。

8
left_index = 2, right_index = 2, middle_index = 2

此时程序因为一直执行else语句而陷入死循环。左右索引始终保持不变。

因此，您需要做的第二个更改是将 while 条件更改为：

while (left_index < right_index)

此时当左索引和右索引相等时，循环就会中断。 您需要做的最后一件事是再次更新您的中间索引。或者您可以使用 left_index 或 right_index（它们相等并不重要）。

最后，您的函数应如下所示：

const int *BinarySearchIter(const int SortedArray[], int key, size_t length) {

    int left_index = 0, right_index = length - 1;

    while (left_index < right_index) {

        int middle = (left_index + right_index) / 2;

        if (SortedArray[middle] < key) {
            left_index = middle + 1;
        } else {
            right_index = middle;
        }
    }

    return SortedArray[right_index] == key ? SortedArray + right_index : NULL;
}

对于递归函数

您唯一需要更改的是：

return BinarySearchRec(SortedArray+(middle + 1)*isBigger, key, (length / 2) + !isBigger * (length % 2));

原因同迭代函数。您需要包括中间元素。对于数组的下半部分，数组长度需要等于 ceil(length / 2)，而对于数组的上半部分，它需要等于 地板（长度/2）.

您也可以这样做：

const int *BinarySearchRec(const int SortedArray[], int key, size_t length) {   
    if (1 == length) return (key == *SortedArray ? SortedArray : NULL);

    int middle = (length + 1) / 2;

    if (key >= SortedArray[middle]) return BinarySearchRec(SortedArray + middle, key, length / 2);
    else return BinarySearchRec(SortedArray, key, middle);
}

我在我的 C 二进制搜索代码中做错了什么？（迭代和递归）

What am I doing wrong in my C binary search code? (iterative & recursive)

c

algorithm

recursion

search

binary-search

对于迭代函数

对于递归函数

我在我的 C 二进制搜索代码中做错了什么？ （迭代和递归）

What am I doing wrong in my C binary search code? (iterative & recursive)

c

algorithm

recursion

search

binary-search

对于迭代函数

对于递归函数

我在我的 C 二进制搜索代码中做错了什么？（迭代和递归）