C++での一致検索

numsと呼ばれる一意の整数のリストがあるとします。標準の二分探索を使用して、まだ正常に検出できる整数の数を検出する必要があります。

したがって、入力が[2,6,4,3,10]の場合、出力は3になります。これは、バイナリ検索を使用して4を検索する場合と同様に、最初に見つけることができます。反復。また、2回の反復後に2と10を見つけることができます。

これを解決するには、次の手順に従います-

• 関数help（）を定義します。これは、ターゲット、配列、および数値を取ります。

• 低：=0

• high：=numsのサイズ-1

• 低い<=高い間、実行-

  • 中：=低+（高-低）/ 2

  • nums [mid]がターゲットと同じ場合、-

    • trueを返す

  • nums [mid]

    • 低：=中+ 1

  • それ以外の場合

    • 高：=中-1

• falseを返す

• メインの方法から、次のようにします-

• ret：=0

• numsの各要素iについて

  • 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