find-duplicate-nlogn-binary-search.cpp

find-duplicate-nlogn-binary-search.cpp

int findDuplicate(vector<int>_&nums) {
	

       int low = 1;

       int high = nums.size() - 1;// 5= 5-1= 4

       [1,2,3,4]


       while(low < high) {

            int mid = (low + high) / 2;

            int count = 0;

            for(int num: nums) {

                if(num <= mid) {

                      count++;
                }
            }      

            if(count > mid) high = mid;

                     else 

                           low = mid + 1;
       } 

       return low;

}