代码之家 › 专栏 › 技术社区 › MEnnabah

高效实现二进制搜索

binary-search c++11 algorithm c++

MEnnabah · 技术社区 · 7 年前

我有一个关于实现二进制搜索的算法测试,该测试在最长2秒的时间内有效。

首先,我实现了二进制搜索的递归版本,但在一些测试用例中,完成这个过程几乎需要3.6秒。然后,我将其更改为迭代版本,但在同一测试用例中需要2.6秒。然而,我认为使用 while loop 这是它花费大量时间的原因。

我的问题是: 我需要改进什么才能达到最多2秒?

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int iterBinarySearch(vector<int> A, int low, int high, int key) {
    int mid;
    while (low <= high) {
        mid = low + ((high - low)/2);
        if (key < A[mid]) {
            high = mid -1;
        } else if (key > A[mid]) {
            low = mid +1;
        } else {
            return mid;
        }
    }
    return -1;
}

int main() {

    vector<int>dict;
    vector<int>keys;

    int dictSize;
    cin >> dictSize;
    while (dictSize--) {
        int val;
        cin >> val;
        dict.push_back(val);
    }

    int keysSize;
    cin >> keysSize;
    while (keysSize--) {
        int val;
        cin >> val;
        keys.push_back(val);
    }

    sort(dict.begin(), dict.end());
    int size = (int)dict.size() -1;
    for(int i = 0; i< keys.size(); ++i) {
        if ((dict[0] > keys[i]) || (dict[size] < keys[i])) {
            cout << "-1" << ' ';
        } else {
            int res = iterBinarySearch(dict, 0, size, keys[i]);
            cout << res << ' ';
        }
    }
    return 0;
}

3 回复 | 直到 7 年前

Useless 7 年前

只有两件事显然是浪费的:

int iterBinarySearch(vector<int> A, int low, int high, int key) 复制向量(您的评论中可能包含100000个元素),而

int iterBinarySearch(const vector<int> &A, int low, int high, int key) (或任何其他const-ref拼写)将直接搜索原始向量,无需复制
您的首字母 push_back 当你提前知道向量的大小时,对于dict和key向量是浪费的:因为你没有告诉向量将有多大,它必须不断调整大小和复制。只需添加
```
    cin >> dictSize;
    dict.reserve(dictSize); // grow to the correct size just once
    while (dictSize--) {
      int val;
      cin >> val;
      dict.push_back(val);
    }
```
钥匙也是一样。

现在,除了这两件事外,理想情况下,你应该试着分析你的代码,而不是仅仅猜测速度慢在哪里。

Gor 7 年前

主要问题是当您将dict参数作为值传递时。

只需将其作为常数参考

int iterBinarySearch(const vector<int> &A, int low, int high, int key) {
    // your code 
}

mid = low + ((high - low)/2);

到

mid = (low + high)/2;

注意:仅当向量大小不大于INT\u MAX/2时,才进行第二次更改。

Aconcagua 7 年前

如前所述,将向量作为常量引用传递是一个主要点,使用 reserve 另一个。完全不分配密钥也可以提高性能:

sort(dict.begin(), dict.end());

int keysSize;
cin >> keysSize;

// this is a constant loop constraint, so move it out, too...
int size = (int)dict.size() - 1;

while (keysSize--)
{
    int val;
    cin >> val;

    if (val < dict[0] || val > dict[size])
    {
        cout << "-1" << ' ';
    }
    else
    {
        int res = iterBinarySearch(dict, 0, size, keys[i]);
        cout << res << ' ';
    }
}
return 0;

您可以保护一个额外的函数调用:

cout << "-1 ";

请注意:在处理本质上不能为负的值(大小、数组索引等)时,我更喜欢有符号数据类型的无符号计数器部分( unsigned int 在您的情况下)。这不会对性能产生任何影响,就像现代二者的互补架构一样,将使用完全相同的操作(除了一些比较之外),只需从数据类型中更清楚地显示变量的意图和(部分)有效范围(需要提及的一个例外:假设您需要int64\u t进行签名,但可以使用uint32\u t,并且您有一个32位架构,例如微控制器– 然后您确实获得了一些最小的性能增益。