คำอธิบายปัญหา
สมมติว่าเรามีอาร์เรย์ที่แสดงองค์ประกอบของลำดับเลขคณิต (Arithmetic Progression) ตามลำดับ มีองค์ประกอบหนึ่งหายไป เราต้องหาองค์ประกอบที่หายไปนั้น เช่นถ้า arr = [2, 4, 8, 10, 12, 14] ผลลัพธ์คือ 6 เพราะ 6 หายไป
เราสามารถแก้ปัญหานี้ได้ด้วยการค้นหาแบบทวิภาค (Binary Search) เราจะไปที่องค์ประกอบกลาง แล้วตรวจสอบว่าความต่างระหว่างกลางและถัดจากกลางเท่ากับ diff เดิมหรือไม่ ถ้าไม่เท่ากัน แสดงว่าองค์ประกอบที่หายไปอยู่ระหว่างดัชนี mid และ mid + 1 ถ้าองค์ประกอบกลางเป็นองค์ประกอบที่ n/2 ของ AP แสดงว่าองค์ประกอบที่หายไปอยู่ในครึ่งขวา มิฉะนั้นอยู่ในครึ่งซ้าย
ตัวอย่างโค้ด (C++)
#include <iostream> using namespace std; #define INT_MAX 999999 class Progression { public: int missingUtil(int arr[], int left, int right, int diff) { if (right <= left) return INT_MAX; int mid = left + (right - left) / 2; if (arr[mid + 1] - arr[mid] != diff) return (arr[mid] + diff); if (mid > 0 && arr[mid] - arr[mid - 1] != diff) return (arr[mid - 1] + diff); if (arr[mid] == arr[0] + mid * diff) return missingUtil(arr, mid + 1, right, diff); return missingUtil(arr, left, mid - 1, diff); } int missingElement(int arr[], int n) { int diff = (arr[n - 1] - arr[0]) / n; return missingUtil(arr, 0, n - 1, diff); } }; int main() { Progression pg; int arr[] = {2, 4, 8, 10, 12, 14}; int n = sizeof(arr) / sizeof(arr[0]); cout << "The missing element is: " << pg.missingElement(arr, n)<<endl; }นำเข้า
[2,4,8,10,12,14]
ผลลัพธ์
The missing element is: 6
