Given an integer array of size N - 1 sorted by ascending order, containing all the numbers from 1 to N except one, find the missing number.
Assumptions
The given array is not null, and N >= 1
Examples
A = {1, 2, 4}, the missing number is 3
A = {1, 2, 3}, the missing number is 4
A = {}, the missing number is 1
class Solution(object):
def missing(self, array):
low = 0
high = len(array) - 1
if len(array) < 1:
return 1
while low <= high:
mid = (low + high)/2
for i in xrange(0,len(array)):
if array[i] != i + 1:
return i+1
else:
i += 1
return array[-1] + 1
