问题是我们第一次尝试为 vector 类执行二进制搜索功能,但我真的不知道这不起作用的原因。有谁知道可能出了什么问题(当数字不在 vector 数组中时状态访问违规)??
//size_ 是数组中已使用元素的数量
int Vector::bsearch(int value) const
{
int first = 0;
int last = size_ - 1;
int Substraction = size_ /2;
while(last >= first)
{
Substraction = first + (last - first) / 2;
if(array_[Substraction] > value)
last = Substraction;
else if(array_[Substraction] < value)
first = Substraction;
else if(array_[Substraction] == value)
return Substraction;
}
return CS170::Vector::NO_INDEX;
}
//已解决
int Vector::bsearch(int value) const
{
unsigned first = 0;
unsigned last = size_ - 1;
unsigned int mid;
if(value < array_[0] || value > array_[size_ - 1])
return CS170::Vector::NO_INDEX;
while(last >= first)
{
mid = first + (last - first) / 2;
if(value < array_[mid])
last = mid - 1;
else if(array_[mid] < value)
first = mid + 1;
else
return mid;
}
return CS170::Vector::NO_INDEX;
}
最佳答案
您没有排除在下一个循环之前刚刚测试的元素。而你选择的变量名,Subtraction
是可怕的。它是一个中点。
int first = 0;
int last = size_-1;
int mid = 0;
while(last >= first)
{
mid = first + (last - first) / 2;
if(value < array_[mid])
last = mid-1; // don't include element just tested
else if(array_[mid] < value)
first = mid+1; // don't include element just tested
else return mid;
}
return CS170::Vector::NO_INDEX
关于c++ - 二进制搜索 C++,STATUS_ACCESS_VIOLATION,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23039436/