Missing Element ใน Sorted Array ใน C++

ปัญหา

ให้ Sorted Array A ของ Unique Numbers หา Missing Number ลำดับที่ K (นับจาก Element แรก)

ตัวอย่าง: A=[4,7,9,10], K=1 → Missing: 5,6,8... → ตัวที่ 1 คือ 5

อัลกอริทึม: Binary Search

Missing Count ระหว่าง Index 0 ถึง i = A[i] - A[0] - i

Binary Search หา Index ที่ Missing Count ≥ K

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int n = nums.size();
        
        // ถ้า K อยู่นอก Array (มากกว่า Missing ทั้งหมดใน Array)
        int total_missing = nums[n-1] - nums[0] + 1 - n;
        if (total_missing < k)
            return nums[n-1] + (k - total_missing);
        
        int left = 0, right = n - 1;
        while (left < right - 1) {
            int mid = left + (right - left) / 2;
            int missing = nums[mid] - nums[left] - (mid - left);
            
            if (missing >= k)
                right = mid;
            else {
                k -= missing;
                left = mid;
            }
        }
        return nums[left] + k;
    }
};

int main() {
    Solution ob;
    vector<int> v = {4, 7, 9, 10};
    cout << ob.missingElement(v, 1) << endl;  // 5
    cout << ob.missingElement(v, 2) << endl;  // 6
    cout << ob.missingElement(v, 3) << endl;  // 8
    cout << ob.missingElement(v, 5) << endl;  // 11 (นอก Array)
    return 0;
}

ผลลัพธ์

5
6
8
11

ความซับซ้อน

• Time: O(log N)
• Space: O(1)

คำอธิบาย Missing Count Formula

ใน Range [left, mid] ควรมีตัวเลข: nums[mid] - nums[left] + 1 ตัว

แท้จริงมี: mid - left + 1 ตัว

Missing = (nums[mid] - nums[left] + 1) - (mid - left + 1) = nums[mid] - nums[left] - (mid - left)