หาตัวเลขที่หายไปใน Sorted Array ของจำนวนติดต่อกันใน C++

แนวคิด

กำหนดอาร์เรย์ array[] ขนาด n จำนวนเต็มที่ต่างกัน เรียงจากน้อยไปมากแบบติดต่อกัน แต่ขาด 1 ตัว หาตัวที่ขาดไป

ตัวอย่าง

• Input: {1, 2, 3, 4, 5, 6, 7, 9} → Output: 8
• Input: {-4, -2, -1, 0, 1, 2} → Output: -3
• Input: {1, 2, 3, 4} → Output: -1 (ไม่มีตัวหาย)

หลักการ

• ความสม่ำเสมอ (Consistency): ความต่างระหว่างอิลิเมนต์กับดัชนีต้องคงที่ = array[0] สำหรับทุกอิลิเมนต์
• ตัวอย่าง: A[]={1,2,3,4,5} → Consistent (A[i]-i = 1)
  C[]={1,2,3,5,6} → Inconsistent ที่ i=3 เพราะ 5-3=2 ≠ 1
• ใช้ Binary Search หาจุดที่ Inconsistent → O(log N)

อัลกอริทึม

1. หาค่ากลาง (mid) ตรวจสอบความสม่ำเสมอ
2. ถ้าสม่ำเสมอ:
   • ถ้า array[mid+1] - array[mid] > 1 → array[mid]+1 คือคำตอบ
   • มิฉะนั้น ค้นหาด้านขวา (low = mid+1)
3. ถ้าไม่สม่ำเสมอ:
   • ถ้า array[mid] - array[mid-1] > 1 → array[mid]-1 คือคำตอบ
   • มิฉะนั้น ค้นหาด้านซ้าย (high = mid-1)

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

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

int findMissing(int array[], int n1) {
    int low = 0, high = n1 - 1;
    int mid1;
    
    while (high > low) {
        mid1 = low + (high - low) / 2;
        
        if (array[mid1] - mid1 == array[0]) {
            if (array[mid1 + 1] - array[mid1] > 1)
                return array[mid1] + 1;
            else
                low = mid1 + 1;
        } else {
            if (array[mid1] - array[mid1 - 1] > 1)
                return array[mid1] - 1;
            else
                high = mid1 - 1;
        }
    }
    return -1;  // ไม่มีตัวหาย
}

int main() {
    int array[] = { -9, -8, -6, -5, -4, -3, -2, -1, 0 };
    int n1 = sizeof(array) / sizeof(array[0]);
    cout << "The Missing Element: " << findMissing(array, n1);
}

ผลลัพธ์

The Missing Element: -7