高效实现二分查找

Question

我有一个关于实现二分查找的算法测试，最长运行时间为 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;
}

Answer 1

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

只需将其作为 const 引用传递即可。

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

2。也尝试更改此行

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

到

mid = (low + high)/2;

NOTE: Make second change only if your vector size is not bigger than INT_MAX / 2.

Answer 2

如前所述，将向量作为 const 引用传递是一个重点，使用 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_t 来表示签名，但可以使用 uint32_t，并且你有一个 32 位架构，例如一个微控制器 – 然后你真的得到了一些最小的性能提升......）。

Answer 3

只有两件事是明显浪费的：

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

int iterBinarySearch(const vector<int> &A, int low, int high, int key)（或任何其他 const-ref 拼写）将直接搜索您的原始向量，不进行复制
当您事先知道大小时，您对 dict 和键向量的初始 push_back 是浪费：因为您没有告诉向量它将有多大，它有继续调整大小和复制。只需添加
```
    cin >> dictSize;
    dict.reserve(dictSize); // grow to the correct size just once
    while (dictSize--) {
      int val;
      cin >> val;
      dict.push_back(val);
    }
```
按键也一样。

现在，除了跳出来的这两件事之外，理想情况下，您应该尝试分析您的代码，而不是仅仅猜测缓慢的地方。

高效实现二分查找

Efficient implementation Binary Search

c++

algorithm

binary-search

c++11