find-duplicate-complexitate-logN.java

find-duplicate-complexitate-logN.java

//solution: log n
//n log n (Array.sort(nums))
//O(n^2)
//O(n)
class Solution {

//[1,3,4,2,2]
	//length  = 5
	//low = 1;
	//high = 5;
	 public int findDuplicate(int[] nums) {
	 	
            int low = 1;

            int high = nums.length - 1;
            //[1,2,3,4,5]

            while( low < high ) {

            	  int mid = (low + high) / 2;//1 + 5 = 6/2 = 3
           
                  int count = 0;

                  for(int num: nums) {

                          if(num <= mid) {

                          	 count++;
                          } 
                  }  

                  if(count > mid) {

                  	  high = mid;

                  } else {
                   
                      low = mid + 1;
                  } 

            }

            return low;

	 }
}