一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0~n-1 之内。在范围 0~n-1 内的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。
思路 1：遍历
最直观的思路是：从左到右遍历一遍数组，比较数字是否等于下标，找出第一个数字不等于下标的数字，其下标就是我们要找的。该算法的时间复杂度是 O(n)。我们还能想出更快的算法。
思路 2：二分查找
看到排序的数组，我们就应该想到二分查找。该算法的思路是：使用二分查找算法找出第一个数字不等于下标的数字，其下标就是问题的解。
由于数组是排序的，数组刚开始的一些数字和其下标是相等的，直到出现某个数字，数字比下标小 1，并且其后的数字诸如此类。
二分查找的过程如下：如果中间的数字等于下标，那么目标在右半边；如果中间的数字比下标大 1，那么比较其前面的数字是否也比下标大 1，如果也大 1，说明目标在在左半边；如果不是，说明中间的数字就是目标数字。
该算法的时间复杂度是 $O(log\,n)$。