c++ - 从整数范围内搜索

Question

我需要从整数列表中查找一个整数。我对它们进行排序并使用 lower_bound 找到给定整数落入的范围。这需要 O(lgn)。有什么办法可以做得比这更好吗？

以下是改进的提示。

1. 给定的列表总是正整数
2. 列表是固定的。没有插入或删除。

一种方法是创建一个数组并在数组中建立索引。这可能不节省空间。我可以使用 unordered_map 吗？我应该定义什么哈希函数？

// Sort in reverse order to aid the lookup process
vector<unsigned int> sortedByRange;
//... sortedByRange.push_back(..)
sort(sortedByRange.begin(), sortedByRange.end(), greater);
Range = (sortedByAddress_.begin() - sortedByRange.end();
std::cout<<"Range :"<<Range<<std::endl;    //prints 3330203948

std::pair<unsigned int, unsigned int> lookup(unsigned int addr){
    pair<unsigned int, unsigned int> result;
    vector<unsigned int>::iterator it = lower_bound(sortedByRange.begin(), 
                                           sortedByRange.end(), addr);
    result.first = *it;
    result.second = *(it++);
    return result;
}      

Answer 1

如果总范围不是很大，您可以构建一个任何方便大小的采样索引数组(您想要多少 RAM？)

因此，例如，如果数据的总范围为 256M，并且您有空闲兆字节，则存储数据范围的每 1K 间隔的位置。然后对于任何给定的数据点，您执行 O(1) (实际上是 O(2) :) )探查索引数组以找到该数据点的最低和最高合理范围，然后您可以对其执行 lowest_bound范围。如果您的范围在大小上变化不大，那应该会为您提供平均恒定时间查找。

如果您不想在这个问题上浪费那么多内存，您可以尝试一对基于平均范围大小和模糊因子的线性估计。如果结果不包含特定数据点，则可以退回到完整的二进制搜索；否则，同样，限制范围内的二进制搜索应该是平均线性时间。

这是第一个建议，以防挥手不够清楚。完全未经测试的代码，甚至没有尝试编译它，而且整数类型的使用至少可以说是草率的。如果你使用它，尽量让它更漂亮。我也应该(但没有)将索引范围的开始限制为 *begin_;如果该值明显大于 0，则应修复它。

// The provided range must be sorted, and value_type must be arithmetic.
template<type RandomIterator, unsigned long size>
class IndexedLookup {
 public:
  using value_type = typename RandomIterator::value_type;
  IndexedLookup(RandomIterator begin, RandomIterator end)
    : begin_(begin),
      end_(end),
      delta_(*(end_ - 1) / size) {
    for (unsigned long i = 0; i < size; ++i)
      index_[i] = std::lower_bound(begin_, end_, i * delta_) - begin_;
      // The above expression cannot be out of range
    index_[size] = end_ - begin_;
  }

  RandomIterator lookup(value_type needle) {
    int low = needle / delta_;
    return std::lower_bound(index_[begin_ + low],
                            index_[begin_ + low + 1],
                            needle);
  }

 private:
  RandomIterator begin_, end_;
  value_type delta_;
  std::array<int, size + 1> index_;
}