写一个二分查找分治算法查找多个数的代码
时间: 2023-04-06 18:02:42 浏览: 59
以下是二分查找分治算法查找多个数的代码:
```
#include <iostream>
#include <vector>
using namespace std;
int binary_search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
vector<int> search_range(vector<int>& nums, int target) {
vector<int> res(2, -1);
int left_idx = binary_search(nums, target - 0.5);
int right_idx = binary_search(nums, target + 0.5);
if (left_idx <= right_idx) {
res[0] = left_idx;
res[1] = right_idx - 1;
}
return res;
}
int main() {
vector<int> nums = {1, 2, 3, 3, 3, 4, 5, 6};
int target = 3;
vector<int> res = search_range(nums, target);
cout << "[" << res[0] << ", " << res[1] << "]" << endl;
return 0;
}
```
这个算法可以在有序数组中查找一个数,并返回该数的下标。如果数组中有多个相同的数,可以返回这些数的范围。