# 1060. Missing Element in Sorted Array

• Time: $O(\log n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: int missingElement(vector& nums, int k) { int l = 0; int r = nums.size(); // # of missing numbers in [nums[0], nums[i]] auto nMissing = [&](int i) { return nums[i] - nums[0] - i; }; // Find the first index l s.t. nMissing(l) >= k while (l < r) { const int m = (l + r) / 2; if (nMissing(m) >= k) r = m; else l = m + 1; } return nums[l - 1] + (k - nMissing(l - 1)); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int missingElement(int[] nums, int k) { int l = 0; int r = nums.length; // Find the first index l s.t. nMissing(l) >= k while (l < r) { final int m = (l + r) / 2; if (nMissing(nums, m) >= k) r = m; else l = m + 1; } return nums[l - 1] + (k - nMissing(nums, l - 1)); } // # of missing numbers in [nums[0], nums[i]] private int nMissing(int[] nums, int i) { return nums[i] - nums[0] - i; } }