Coincidence Search in C++: นับจำนวนที่หาได้ด้วย Binary Search บน Array ไม่ได้เรียง

กำหนด array nums ที่มีค่าไม่ซ้ำกัน ต้องนับว่ามีจำนวนกี่ตัวที่ "หาได้" หากใช้ Binary Search มาตรฐานบน array นี้ (โดยที่ array ไม่ได้เรียงลำดับ)

ตัวอย่าง: [2,6,4,3,10] → Output: 3

คำอธิบาย: Binary Search หา 4 เจอทันที (mid = index 2), หา 2 และ 10 เจอหลัง 2 รอบ

วิธีแก้ปัญหา

สำหรับแต่ละค่าใน array ให้รัน Binary Search จริงบน array เดิม
นับจำนวนที่คืน true

หมายเหตุ: Binary Search จะทำงานถูกต้องก็ต่อเมื่อค่าที่หาอยู่ที่ตำแหน่ง mid หรือเส้นทางการค้นหาตรงกับลำดับของ array

ตัวอย่างโค้ด C++

#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 x : nums) ret += help(x, nums);
        return ret;
    }
};

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

Input

{2,6,4,3,10}