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