【重点】【二分搜索】剑指 Offer 53 - II：0～n-1中缺失的数字

力扣，https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/

二分搜索

class Solution:
    def takeAttendance(self, records: List[int]) -> int:
        l, r = 0, len(records) - 1
        while l <= r: # 退出循环的条件: l == r+1
            mid = (l+r) // 2
            if records[mid] == mid: # 答案肯定在[mid+1, r]之内
                l = mid + 1
            elif records[mid] > mid: # 答案可能是mid, 但r=mid会有死循环, 所以r=mid-1
                r = mid - 1
            # 显然不会出现 records[mid] < mid 的情况
        
        return l

Java

线性扫描，一般情况

class Solution {
    public int takeAttendance(int[] records) {
        boolean[] visited = new boolean[records.length + 1];
        Arrays.fill(visited, false);
        for (int i : records) {
            visited[i] = true;
        }
        for (int i = 0; i < visited.length; ++i) {
            if (!visited[i]) {
                return i;
            }
        }

        return -1;
    }
}

solution2

二分搜索

class Solution {
    public int takeAttendance(int[] records) {
        return binarySearch(0, records.length - 1, records);
    }

    public int binarySearch(int left, int right, int[] records) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;// 返回right + 1也可
    }
}