- first and last are not missing.

Use modded binary search. Converge start and end to the numbers between which the missing number is (i.e. start +1 = end).

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

int findMissing(a): if a == null || a.length() < 2: throw start = 0 end = a.length() -1 delta = (a[end] - a[start]) /a.length() while start +1 != end: mid = start + (end - start)/2 midValue = a[start] + delta*(mid-start) if a[mid] == midValue: start = mid else: end = mid missing = a[start] + delta return missing[Hat tip to JV]

## No comments:

## Post a Comment