C++의 우연 검색

nums라고 하는 고유한 정수 목록이 있다고 가정합니다. 표준 이진 검색을 사용하여 여전히 성공적으로 찾을 수 있는 정수의 수를 찾아야 합니다.

따라서 입력이 [2,6,4,3,10]과 같으면 출력은 3이 됩니다. 마치 이진 검색을 사용하여 4를 찾는 것처럼 처음에는 찾을 수 있습니다. 반복. 또한 두 번의 반복 후에 2와 10을 찾을 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

help() 함수를 정의하면 대상, 배열 및 숫자가 필요합니다.
낮음 :=0
high :=숫자 크기 - 1
낮음 <=높음, 수행 -
- 중간 :=낮음 + (높음 - 낮음) / 2
- nums[mid]가 target과 같으면 -
  - true를 반환
- nums[mid]
  - 낮음 :=중간 + 1
- 그렇지 않으면
  - 높음 :=중간 - 1
거짓을 반환
기본 방법에서 다음을 수행하십시오 -
ret :=0
숫자의 각 요소 i에 대해
- ret :=ret + help(i, nums)
리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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}