Tìm kiếm trùng hợp trong C++

Cho mảng số nguyên nums không trùng lặp. Cần đếm số lượng phần tử mà nếu dùng tìm kiếm nhị phân (binary search) tiêu chuẩn trên mảng chưa sắp xếp này thì vẫn tìm thấy được.

Ví dụ: [2,6,4,3,10] → 3 (có thể tìm thấy 4, 2, 10).

Giải thuật:

• Với mỗi phần tử target trong mảng, chạy binary search trên mảng gốc.
• Đếm số lần tìm kiếm thành công.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool help(int target, vector<int>& nums) {
        int low = 0, 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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2,6,4,3,10};
    cout << (ob.solve(v));
}

Đầu vào

{2,6,4,3,10}

Đầu ra

3