1

我有一个数据表，如下所示。请注意，keyID 可以重复。我在向量结构中收集了以下数据，这些数据是排序的。

struct myData {
   int keyID;
   int value;
}

vector<myData> vecReadFromFile;

现在用户输入一个特定的 keyID，我必须检查该值是否存在于向量中，如果存在我必须返回该值。如果不是我必须检查它落在哪些值之间，例如如果用户输入 120030，值在 120028 和 120039 之间，我应该得到这些值的索引，即在这个例子中，lowerIndex 和 upperIndex 为“2”和“3”（作为向量索引从 0 开始）

如果用户输入较少的 keyID，即 120001，则不返回任何值。同样，用户输入的 keyID 大于最后一个键值，然后返回不同的错误代码。

基本上我想有效地找到给定键值的索引范围。我添加的代码似乎不适用于上面的例子我提到了什么是错误？

我可以更改逻辑以使用 STL 提供的算法。请建议。

我们如何在 C++ 中有效地实现这个算法？请求以示例代码作为函数。注意这里我会在我的项目中多次调用函数，所以它必须有效。

keyID   Value   

120002  10  
120025  20  
120028  25  
120039  30  
120042  -   
120048  40  
120052  50  
120112  60  
120117  70  
120123  70  
120126  80  
120130  90

我这里有一些代码

 //==========================================================================
// FindBounds
bool FindBounds(const KEY& cTarget, UINT& uLower, UINT& uUpper)
{
  uLower = -1;
  uUpper = -1;

  // start with full range of data.
  uLower = 0;
  uUpper = m_uCount-1; // Here I have m_uCount as vector.size()

 // narrow the bounds as much as possible.
 while (uUpper - uLower > 1 && cTarget != m_pKeys[uLower])
 {  
    // split the range in half and discard the half that the key does not belong to. 
    UINT uBound = uUpper - (uUpper-uLower)/2;
    // keep the lower range.
    if (KeyInRange(uLower, uBound, cTarget))
    {
       uUpper = uBound;
    }
    // keep the upper range.
    else
    {
      uLower = uBound;
    }
 }

}

bool KeyInRange(UINT uLower, UINT uUpper, const KEY& cTarget)
{
    // check if target is within range.
    if (m_pKeys[uLower] <= cTarget)
    {
    if (m_pKeys[uUpper] > cTarget || (m_pKeys[uLower] == cTarget && m_pKeys[uLower] == m_pKeys[uUpper]))
    {
            return true;
    }
     }
    // target is not within range.
    return false;
}

感谢您的时间和帮助

4

3 回答 3

5

有std::equal_range算法。

于 2012-08-31T12:55:26.053 回答
5

std::lower_bound()来自 STL，<algorithm>标题： http ://en.cppreference.com/w/cpp/algorithm/lower_bound

于 2012-08-31T12:58:49.300 回答
1

1）我认为，如果您要通过键查找某些值，最好选择 STL 容器multiset，它允许键重复。

2）查看方法lower_bound()，upper_bound()它们可能适用于您尝试做的事情

于 2012-08-31T12:59:57.393 回答