如题：在一组有序的数组中找出缺失的数据，如[1,3,5,6,7,9,10]中缺失了数据2，4，8，只能使用一次遍历。
网上有很多缺失一个数据的资料，在这里就不累述。
看到有序的数组应该是确定使用二分查找，将数组一分为二，分而治之。利用递归方式寻找缺失的数据，直到找到两个相邻数据之间有缺失为止。以下利用Java 代码实现。
//假设不缺失的数组
private final static int[] targetArray = new int[]{1,2,3,4,5,6,7,8,9,10};
public static void findLost(int[] array,int start ,int end){
int lostLength = (array[end]-array[start])-(end-start);
if (lostLength<=0) { //缺失数据为0时退出
return;
}else{
if ((end-start)==1) { //当有缺失数字并且找到位置时打印出缺失数字
System.out.print(Arrays.toString(Arrays.copyOfRange(
targetArray,array[start],array[end]-1)));
return;
}
int key = start + (end - start)/2;
findLost(array,start,key);
findLost(array,key,end);
}
}
此算法的时间复杂度为O(log(n))。
