在数组中寻找上限

Question

我正在尝试使用变量“ sum”作为上限，在数组“ size”中获取最近的上限（除非找到等效值）的索引，然后在相同的索引处在数组“ value”中查找该值。
例如：如果“ sum”的值为270，则我的程序应该找到位于size中的索引6处的值280，并输出相应value[6]的值。

#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

int main()
{
    double x = 0;
    double y = 0;
    double sum = 0;
    double size[27] = {24, 28, 32, 38, 48, 240, 280, 320, 360, 380,
                       420, 480, 560, 600, 640, 700, 720, 800, 840,
                       960, 980, 1120, 1200, 1280, 1440, 1680, 1920};

    double value[27] = {.0022, .0026, .0029, .0035, .0044, .0219,
                        .0256, .0292, .0328, .0384, .0438, .0513,
                        .0547, .0584, .0641,.0656, .073, .0766,
                        .0875, .0877, .0897, .1023, .1094, .1169,
                        .1313, .1531, .175};

    cout << "Enter width: " << endl;
    cin >> x;
    cout << "Enter height: " << endl;
    cin >> y;

    x = ceil(x) + 3;
    y = ceil(y) + 3;

    sum = x * y;
}

- user3867859

---

要是有一个像std::upper_bound这样的命名函数就好了……还有，value数组是怎么回事？你为什么要用double初始化它，然后再将这些（现在都是0）值复制到size中呢？ - user657267

你使用memcpy而不是std::copy有什么原因吗？ - user1804599

建议先读一本正经的书。 - Bartek Banachewicz

@Naseef 是的，已经排序好了。 - user3867859

@JamesKanze 如果找不到确切的值，就必须找到上限。 - user3867859

Answer 1

将您的代码更改为以下内容 -

    double x = 0;
    double y = 0;
    double sum = 0;
    int size[27] = {24, 28, 32, 38, 48, 240, 280, 320, 360, 380,
    420, 480, 560, 600, 640, 700, 720, 800, 840, 960, 980, 1120, 1200, 1280, 1440, 1680, 1920};
    double value[27] = {.0022, .0026, .0029, .0035, .0044, .0219,
    .0256, .0292, .0328, .0384, .0438, .0513, .0547, .0584, .0641,.0656, .073, .0766, .0875, .0877, .0897, .1023, .1094, .1169, .1313, .1531, .175};

    cout << "Enter width: " << endl;
    cin >> x;
    cout << "Enter height: " << endl;
    cin >> y;

    x = ceil(x) + 3;
    y = ceil(y) + 3;

    sum = x * y;

    for (int i=0;i<27;i++)
    {
        if (size[i]>=sum)
        {
          cout<<value[i]<<endl; 
          break;
        }
        else if(i==26)
        {
            cout<<"No upper Bound find\n";
        }
    }

还有其他解决方法。但是你说你是初学者，我已经给出了简单的暴力解决方案。 :)

- Naseef Chowdhury

---

如果我使用 x = 15.4，y = 16，sum = 19*19 = 361。在数组大小方面，380 是最接近的值，它被放置在 size[10]，并且 value[10] = .0384，而此程序输出为 .0328？ - user3867859

不过，感谢您提供的代码。我会仔细查看并看看如何修复它以解决问题。 - user3867859

@user3867859 现在请检查一下，已经修复了。 - Naseef Chowdhury

"[pos]" 是什么意思？ - user3867859

请提供需要翻译的英文内容。 - Naseef Chowdhury

问题解决了吗？ - Naseef Chowdhury

Answer 2

要获取上限的索引，只需使用 std::upper_bound 如下所示（需要确保范围至少部分排序）：

// Get iterator to upper bound.
auto it = std::upper_bound(std::begin(size), std::end(size), sum);

// Get index by iterator subtraction.
std::size_t index = it - std::begin(size);

然后使用index，例如：

std::cout << value[index] << std::endl;

- Felix Glas

Answer 3

我认为最好通过以下方式获取上限的索引：

upper_bound(size, size+27, sum) - size

获取上限的值：

int index = upper_bound(size, size+27, sum) - size;
cout << size[index] << endl;

我使用以下代码测试性能。每个在 for 循环下的一行代码都会给出上限所在的索引。

#include <bits/stdc++.h>
using namespace std;

int main(){
    unsigned char Array[8] = {5, 10, 15, 20, 25, 30, 35, 40};
    unsigned char* it = upper_bound(Array, Array+8, 23);
    for(int i = 0 ;i < 100000000; ++i)//0.46s
        distance(Array, it);
    for(int i = 0 ;i < 100000000; ++i)//0.21s
        it - begin(Array);
    for(int i = 0 ;i < 100000000; ++i)//0.19s
        it - Array;
}

在我的测试中，最后一个是最快的。

- fmnijk

---

非常干净！您能详细解释一下这个操作符是如何工作的吗？迭代器实际上是int类型，它们的值按顺序排列吗？ - Kennith

Answer 4

最简单的方法可以用2行代码实现：

auto size_ub = std::upper_bound(std::begin(size), std::end(size), sum);
int idx = std::distance(std::begin(size), size_ub);

cout << value[idx] << endl;

请注意，size必须相对于总和进行分区。你的示例中的排序数组满足这个条件。

- bolov