ধরুন আমাদের একটি অ্যারে আছে যা ক্রমানুসারে গাণিতিক অগ্রগতির উপাদানগুলিকে উপস্থাপন করে। একটি উপাদান অনুপস্থিত. আমাদের অনুপস্থিত উপাদানটি খুঁজে বের করতে হবে। তাই যদি arr =[2, 4, 8, 10, 12, 14], আউটপুট 6 হয়, যেমন 6 অনুপস্থিত।
বাইনারি অনুসন্ধান ব্যবহার করে, আমরা এই সমস্যার সমাধান করতে পারি। আমরা মিডল এলিমেন্টে যাব, তারপর পরীক্ষা করে দেখব যে মাঝামাঝি এবং মাঝামাঝি এর পরের পার্থক্যটি ডিফের মতই আছে কি না। যদি না হয়, তাহলে অনুপস্থিত উপাদানটি সূচকের মধ্য এবং মধ্য + 1-এর মধ্যে উপস্থিত থাকে। যদি মধ্যবর্তী উপাদানটি AP-এর n/2 তম উপাদান হয়, তাহলে অনুপস্থিত উপাদানটি ডান অর্ধেক, অন্যথায় বাম অর্ধেকে থাকে।
উদাহরণ
#include <iostream>
using namespace std;
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);
} আউটপুট
The missing element is: 6
