package offer;
/**
 * 二分查找的思想來找到數(shù)組中重復的數(shù)字，時間復雜度在o(nlogn)-o(n^2)
 */
public class FindDuplicate3 {
 public static void main(String[] args) {
 int numbers[] = {0,1,2,3,4,4,6,7};//數(shù)組中的數(shù) 大小從0 到 numbers.length-1
 findDuplicate(numbers,0,numbers.length-1);
 }
 static void findDuplicate(int numbers[],int left,int right){
 if (numbers == null || numbers.length == 0)
 return;
 int mid; 
 while(left<=right)
 { 
 System.out.println("Find duplicate from "+left+" to "+right);
 mid=(left+right)/2;
 if(left==right)//當兩個下標值相等結(jié)束循環(huán)
 {
  if(countNumberInRange(numbers,left,right)>1)
  {  
  System.out.println(left);
  break;
  }
  else break;
 }
 //以下通過計算在指定區(qū)間數(shù)組中數(shù)字的個數(shù)與區(qū)間的長度對比來確定數(shù)組中是否有重復數(shù)字
 if(countNumberInRange(numbers,left, mid)>(mid-left+1))//如果數(shù)字區(qū)間從left到 mid的數(shù)字個數(shù)大于mid-left+1 則本區(qū)間肯定與重復數(shù)字
 {
  right=mid;
 }
 else if(countNumberInRange(numbers,mid+1, right)>(right-mid))//如果數(shù)字區(qū)間從mid+1到right的數(shù)字個數(shù)大于right-mid則本區(qū)間肯定有重復數(shù)字
 {
  left=mid+1;
 }
 else if(countNumberInRange(numbers,left, mid)==(mid-left+1) && countNumberInRange(numbers,mid+1, right)==(right-mid))
 {//因為上兩個判斷不能確定區(qū)間內(nèi)是每個數(shù)字各出現(xiàn)了一次還是某個數(shù)字出現(xiàn)了兩次，所以當左右區(qū)間長度與數(shù)字個數(shù)相等時不能排除仍然有重復數(shù)字
  if(countNumberInRange(numbers,right,right)>1)//判斷最后一個數(shù)字出現(xiàn)次數(shù)是否是多次
  {
  System.out.println(right);
  break;
  }
  else//縮減區(qū)間
 right=right-1;
 }
 }
 
 }
 //計算數(shù)組中在from到to區(qū)間數(shù)字的個數(shù)
 static int countNumberInRange(int numbers[],int from,int to)
 {
 int count=0;
 if(numbers==null || numbers.length==0)
 return 0;
 for(int i=0;i<numbers.length;i++)
 {
 if(numbers[i]>=from && numbers[i]<=to)
 count++;
 }
 return count;
 }
}