1060. Missing Element in Sorted Array

 一刷 07/2022

Version #1 Binary search for offset

Time O(logN)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Missing Element in Sorted Array.

Memory Usage: 58.1 MB, less than 64.10% of Java online submissions for Missing Element in Sorted Array.

class Solution {

    public int missingElement(int[] nums, int k) {

        // 4 5 6 7 8 9

        // 4     7   9   expected = index i - index 0 + nums[0] = 4 + 2 = 6 -> 9 - 6 = 3

        int start = 0, end = nums.length - 1;

        while (start + 1 < end) { // find the last index whose diff is smaller than k

            int mid = start + (end - start) / 2;

            int offset = nums[mid] - (mid + nums[0]);

            if (offset < k) {

                start = mid;

            } else {

                end = mid - 1;

            }

        }

        // start end

        int endOffset = nums[end] - (end + nums[0]);

        if (endOffset < k) {

            return nums[end] + k - endOffset;

        }

        int startOffset = nums[start] - (start + nums[0]);

        return nums[start] + k - startOffset;

    }

}