หาดัชนีของสมาชิกเพิ่มเติมในอาร์เรย์ที่เรียงแล้วใน C++

โจทย์

ได้รับอาร์เรย์ที่เรียงแล้ว 2 อัน arr1 (ขนาด n) และ arr2 (ขนาด n+1) เหมือนกันทุกตัวยกเว้น 1 ตัว ทางเราต้อง หาดัชนีของสมาชิกเพิ่มเติมใน arr2

ตัวอย่าง

Input: arr1 = {3,5,7,8,9,12}, arr2 = {3,4,5,7,8,9,12}

Output: 1 (ค่าที่ดัชนี 1 คือ 4)

แนวทางแก้ปัญหา

วิธี 1: Linear Search เปรียบเทียบคู่ต่อคู่ จนกว่าจะเจอค่าที่ต่างกัน

วิธี 2: Binary Search (ดีกว่า) ใช้ข้อเท็จจริงว่าก่อนสมาชิกเพิ่มเติม ดัชนีตรงกัน หลังจากนั้นจะเลื่อน

วิธี 3: ผลรวม (Sum Difference) หาผลต่างของผลรวม = ค่าสมาชิกเพิ่มเติม แล้วค้นหาดัชนี

โปรแกรมตัวอย่าง (Binary Search)

#include <iostream>
using namespace std;

int findExtraElement(int arr1[], int arr2[], int n) {
    int extraIndex = n;
    int start = 0, end = n - 1;
    while (start <= end) {
        int mid = (start + end) / 2;
        if (arr2[mid] == arr1[mid]) start = mid + 1;
        else { extraIndex = mid; end = mid - 1; }
    }
    return extraIndex;
}

int main() {
    int arr1[] = {3, 5, 7, 8, 9, 12};
    int arr2[] = {3, 4, 5, 7, 8, 9, 12};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int extraIndex = findExtraElement(arr1, arr2, n);
    cout << "The extra element is at index (" << extraIndex << ") and the value is " << arr2[extraIndex];
    return 0;
}

ผลลัพธ์

The extra element is at index (1) and the value is 4