查找等差数列中的缺失项.
e.g.Input: arr[] = {2, 4, 8, 10, 12, 14}
Output: 6
Input: arr[] = {1, 6, 11, 16, 21, 31};
Output: 26.
采用binary search. 若是arr[mid] - arr[left] == (mid - left) * diff, 说明missing 部分在mid右侧.
否则missing部分在包括mid的左侧.
Time complexity: O(logn). Space: O(1).
public class Main {
public static void main(String[] args) {
try{
int [] arr1 = {2, 4, 8, 10, 12, 14};
int [] arr2 = {1, 6, 11, 16, 21, 31};
int [] arr3 = {1, 6};
System.out.println(findMissing(arr1));
System.out.println(findMissing(arr2));
System.out.println(findMissing(arr3));
}catch(IllegalArgumentException e){
System.out.println(e.getMessage());
}
}
private static int findMissing(int [] arr) throws IllegalArgumentException{
if(arr == null || arr.length < 3){
throw new IllegalArgumentException("Invalid input!");
}
int len = arr.length;
int l = 0;
int r = len-1;
int diff = (arr[r] - arr[l])/len;
System.out.println(diff);
while(l <= r){
int mid = l+(r-l)/2;
if(arr[mid] - arr[l] == (mid-l)*diff){
l = mid+1;
}else{
r = mid;
}
}
return arr[r] - diff;
}
}