class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < nums.size(); i++) {
            if(nums[i] < 0 || nums[i] > n-1) return -1;
        }
        for (int i = 0; i < nums.size(); i++) {
            while(nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
            if(nums[i] != i) return nums[i];

        }
        return -1;
    }
};

//中间数取(L+R)/2或者L的时候，分区间为(L,J)(j+1,R)
//中间数取(L+R+1)/2或者R时，分区间为(L,i-1)(i,R)