我做错了什么？原型是不可变的。我需要写这两个函数，这就是我写的。他们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)
对于迭代函数
让我们思考一下您的代码在做什么。您有一个由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(，对于数组的上部，数组长度必须等于floor(length/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);
}