c++ - 二进制搜索 C++,STATUS_ACCESS_VIOLATION

标签 c++ vector binary-search

问题是我们第一次尝试为 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/

相关文章:

java - 编译器错误? Java二分查找

java - ArrayList BinarySearch

c++ - 读取多个列表

c++ - 用于 ASIO 写入的十六进制字符串到字节

c++ - 对 C++ 中的虚拟基类感到困惑

c++ - C++中的 vector 持久性和 transient

C++ 为什么我的示例程序不能创建输出文件?

c++ - 如何检查派生类对象是否已存储在 vector 中?

c++ - 理论 - 如何判断元素是否重叠?

c++ - 如何在C++中从成对的排序 vector 中获得与给定值有关的相应对