剑指 Offer 53 - II. 0~n-1中缺失的数字

​​​​​​剑指 Offer 53 - II. 0～n-1中缺失的数字 - 力扣（LeetCode） (leetcode-cn.com)

如果把不在数组中的那个数字记为m，那么所有比m小的数字的下标都与它们的值相同。因此我们只需要找出数组中第一个值和下标不相等的元素即可。使用二分查找。

class Solution {
public:
    int missingNumber(vector& nums) {
        if (nums[0]) return 0;

        int beg = 0, end = nums.size(), mid, halfsize;
        while (halfsize = (end - beg) / 2) {
            mid = beg + halfsize;
            nums[mid] == mid ? beg = mid : end = mid;
        }
        return end;
    }
};