C ++中的重合搜索
假设我们有一个称为nums的唯一整数列表。我们必须找到使用标准二进制搜索仍然可以成功找到的整数数量。
因此，如果输入类似于[2,6,4,3,10]，则输出将为3，就好像我们使用二进制搜索来查找4一样，我们可以在第一次迭代时找到它。经过两次迭代，我们还可以找到2和10。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数help()，它将以目标，一个数组和数字，
低：=0
高：=nums的大小-1
当低<=高时，执行-
高：=中-1
低：=中+1
返回真
中：=低+（高-低）/2
如果nums[mid]与目标相同，则-
如果nums[mid]<目标，则-
除此以外
返回假
从主要方法中，执行以下操作-
ret：=0
对于数字中的每个元素
ret：=ret+help(i,nums)
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool help(int target, vector<int> & nums) {
int low = 0;
int high = nums.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target)
return true;
if (nums[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return false;
}
int solve(vector<int> & nums) {
int ret = 0;
for (int i : nums) {
ret += help(i, nums);
}
return ret;
}
};
main() {
Solution ob;
vector<int> v = {2,6,4,3,10};
cout << (ob.solve(v));
}输入项
{2,6,4,3,10}输出结果
3