- first and last are not missing.

Use modded binary search. Check to see if the missing is right before or right after mid.

s m e m e 0 1 2 3 4 5 2 4 8 10 12 14 s m s m e 0 1 2 3 4 5 6 2 4 6 8 10 12 16

(a): if a == null || a.length() == 0: throw missing = -1 n = a.length() delta = (a[n-1] - a[0]) /n start = 0, end = n-1 while start < end: mid = start + (end-start)/2 if a[mid+1] - a[mid] != delta: missing = a[mid] +delta break if mid-1 >= 0 && a[mid] - a[mid-1] != delta: missing = a[mid] -delta break midvalue = a[start] + (mid-start)*delta if a[mid] == midvalue: start = mid +1 else: end = mid -1 return missing[Hat tip to JV]

## No comments:

## Post a Comment