একটি সর্টেড অ্যারে দেওয়া আছে যেখানে সব উপাদান ক্রমাগত কিন্তু একটি মিসিং। O(log N) তে বাইনারি সার্চ দিয়ে মিসিং এলিমেন্ট বের করতে হবে।
উদাহরণ
arr[] = {1,2,3,4,5,6,7,9} → Missing: 8
arr[] = {-4,-2,-1,0,1,2} → Missing: -3
arr[] = {1,2,3,4} → -1 (কোনো মিসিং নেই)
অ্যালগরিদম
- কনসিস্টেন্সি চেক:
arr[i] - i == arr[0]সব индеক্সে সত্য হলে কনসিস্টেন্ট। - মিডেল এলিমেন্ট চেক করুন: কনসিস্টেন্ট হলে ডানে, ইনকনসিস্টেন্ট হলে বামে যান।
- মিডের সাথে পরের/আগের এলিমেন্টের ডিফারেন্স > ১ হলে মিসিং এলিমেন্ট পাওয়া যায়।
C++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
int findMissing(int arr[], int n) {
int low = 0, high = n-1;
while (high > low) {
int mid = low + (high - low)/2;
if (arr[mid] - mid == arr[0]) {
if (arr[mid+1] - arr[mid] > 1) return arr[mid] + 1;
low = mid + 1;
} else {
if (arr[mid] - arr[mid-1] > 1) return arr[mid] - 1;
high = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {-9,-8,-6,-5,-4,-3,-2,-1,0};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The Missing Element: " << findMissing(arr, n);
return 0;
}
আউটপুট: The Missing Element: -7
