剑指offer——570~n-1中缺失的数字

题目：0~n-1中缺失的数字。

　　一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0~n-1之内。

　　在范围0~n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

题解：

　　使用二分法即可。

 1 int findLostNum(const vector<int> &data)
 2 {
 3     if (data.size() == 0)return -1;
 4     int L = 0, R = data.size() - 1, M;
 5     if (data[R] == R)return -1;
 6     while (L >= 0 && R < data.size() && L <= R)
 7     {
 8         M = (R - L) / 2 + L;
 9         if (data[M] == M)L = M + 1;
10         else if (data[M] > M)
11             if (M > 0 && data[M - 1] == M-1)return M;
12             else if (M == 0)return 0;
13             else R = M - 1;
14     }
15     return -1;
16 }