1060. Missing Element in Sorted Array

1. use bucket

O(n)

```java
class Solution {
    public int missingElement(int[] nums, int k) {
        boolean[] bucket = new boolean[nums[nums.length-1]+1];

        for (int i = 0; i < nums[0]; i++) {
            bucket[i] = true;
        }
        for (int num : nums) {
            bucket[num] = true;
        }
        int count = k;
        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i] == false) {
                count--;
            }
            if (count == 0) {
                return i;
            }
        }
        return bucket.length - 1 + count;
    }
}
```

use Binary search

use same way as 1539, but change the start part( 因為這題不是 1 開頭, 可以是任意數字開始）

T: O(logn)

S: O(1)

class Solution {
    public int missingElement(int[] nums, int k) {
        int start = nums[0];
        
        int left = 0;
        int right = nums.length;
        
        while (left < right) {
            int mid = left + (right - left)/2;
            int missing = nums[mid] - mid - start;
            if (missing >= k) {
                right = mid;
            } else {
                left = mid+1;
            }
        }
        return (start-1) + left + k;
    }
}

/*
0 1 2 3
4 5 6 7

nums[i] - i - nums[0]
*/