我想对一个整数数组进行二分查找。我确保数组是递增排序的。但是我的功能并没有跟踪所有的案例,一些检查失败了。我在这里错过了什么?
Value
代表我要查找的整数。
bool search(int value, int array[], int n)
{
int left = 0;
int right = n - 1;
int middle = (left + right) / 2;
while (right >= left)
{
if (array[middle] == value)
return true;
else if (array[middle] < value)
right = middle;
else if (array[middle] > value)
left = middle + 1;
middle = (left + right) / 2;
}
return false;
}
我的猜测是无法预测某些左边界或右边界情况。我也不喜欢 while
条件。
最佳答案
你左右混了,如果array[middle] < value
你必须改变left
.
bool search(int value, int array[], int n)
{
int left = 0;
int right = n - 1;
int middle = left + (right - left) / 2;
while (right >= left)
{
if (array[middle] == value)
return true;
else if (array[middle] > value)
right = middle - 1;
else if (array[middle] < value)
left = middle + 1;
middle = (left + right) / 2;
}
return false;
}
进一步的改进可以是:
您可以排除
middle
在else
部分,因为你已经证明它不是正确的值 (right = middle;
=>right = middle - 1;
)第二个
else if
可以用else
代替.如果它不是该值并且不小于您不必测试它是否更大。
关于c - 如何实现整数数组的二进制搜索?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41897606/