1. 二分查找:在N个无序整数里面查找M个指定整数
时间: 2023-08-10 18:04:12 浏览: 88
好的,针对您的问题,我可以给出以下的二分查找算法实现:
```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> binary_search(vector<int>& nums, vector<int>& targets) {
vector<int> res;
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < targets.size(); ++i) {
int left = 0, right = n - 1;
bool flag = false;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == targets[i]) {
res.push_back(mid);
flag = true;
break;
} else if (nums[mid] < targets[i]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (!flag) {
res.push_back(-1);
}
}
return res;
}
int main() {
vector<int> nums = {3, 1, 4, 2, 5};
vector<int> targets = {1, 3, 6};
vector<int> res = binary_search(nums, targets);
for (int i = 0; i < res.size(); ++i) {
cout << res[i] << " ";
}
cout << endl;
return 0;
}
```
上述代码使用了 STL 库中的 sort 函数对原始数组进行排序,时间复杂度为 O(NlogN);然后使用二分查找算法,时间复杂度为 O(MlogN),其中 M 表示指定整数的个数。因此,总时间复杂度为 O((M+N)logN)。
另外,上述代码中的 res 数组中保存了每个指定整数在原始数组中的下标,如果原始数组中不存在对应的指定整数,则返回 -1。