287. Find the Duplicate Number

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // [1:n] -> [1:n/2] & [n/2+1: n]
        int left = 1;
        int right = nums.size() - 1;

        while (left < right)
        {
            int mid = left + (right - left) / 2;
            auto count = count_if(nums.begin(), nums.end(), [left, mid](const int &num){
                return num >= left && num <= mid;
            });

            if (count > mid - left + 1)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }

        return right;
    }
};