c++ - 从数组中查找元素

Question

我有一个跨度如下的数组。所以要理解的例子是考虑一个有 6 个面的 block 。该数组包含此数组中的索引，特定颜色的面将从该索引开始。

array[0] 0
array[1] 2
array[2] 4
array[3] 5

所以这意味着颜色 0 用于面 0 和 1，颜色 1 用于面 2 和 3， 颜色 2 仅适用于面 4

但数组并不总是这个样子。如果有一个只有一种颜色的 block ，则数组看起来像

array[0] 0
array[1] 1 

这意味着面 0 的颜色为 0，面 1,2,3,4,5 的颜色为 1

我会得到一个输入作为面号，需要找到相应的颜色

我用for循环试过了

for (int index = 0; index < array.size(); ++index) 
{ 
    if (array[index] == input) 
    { 
        return index; 
    } 
    if (array[index] < input) 
    { 
        return index - 1; 
    } 
}

但答案并不总是正确的。这可以用 while 来完成吗？请帮忙

Answer 1

据我了解，您想找到小于或等于给定输入的数组的最大索引。

然后您可以将以下内容与二进制搜索一起使用。

std::size_t getIndexFor(const std::vector<int>& v, int input)
{
    auto it = std::lower_bound(v.begin(), v.end(), input);
    if (it != v.begin() && (it == v.end() || *it != input)) {
        --it;
    }
    return std::distance(v.begin(), it);
}

Demo

更简单(和线性)的方式:

std::size_t getIndexFor(const std::vector<int>& v, int input)
{
    auto it = std::find_if(v.begin(), v.end(), [&](int e){ return e > input;});
    if (it == v.begin()) {
        throw std::runtime_error("input not handled");
    }
    --it;
    return std::distance(v.begin(), it);
}

Demo