ধরুন আমাদের n উপাদান সহ একটি অ্যারে A আছে। এবং উপাদানগুলি সাজানো হয়। আমাদের প্রদত্ত পূর্ণসংখ্যার নিকটতম মান খুঁজে বের করতে হবে। অ্যারেতে ডুপ্লিকেট মান এবং ঋণাত্মক সংখ্যা থাকতে পারে। সুতরাং যদি অ্যারেটি [2, 5, 6, 7, 8, 8, 9] এর মত হয় এবং লক্ষ্য সংখ্যা 4 হয়, তাহলে নিকটতম উপাদান হল 5।
আমরা প্রদত্ত অ্যারের মধ্য দিয়ে অতিক্রম করে এটি সমাধান করতে পারি এবং প্রতিটি উপাদানের সাথে বর্তমান উপাদানের পরম পার্থক্য ট্র্যাক করতে পারি। অবশেষে সেই উপাদানটি ফেরত দিন যার ন্যূনতম পরম পার্থক্য রয়েছে।
উদাহরণ
#include<iostream>
#include<list>
using namespace std;
int getNearest(int x, int y, int target) {
if (target - x >= y - target)
return y;
else
return x;
}
int getNearestElement(int arr[], int n, int target) {
if (target <= arr[0])
return arr[0];
if (target >= arr[n - 1])
return arr[n - 1];
int left = 0, right = n, mid = 0;
while (left < right) {
mid = (left + right) / 2;
if (arr[mid] == target)
return arr[mid];
if (target < arr[mid]) {
if (mid > 0 && target > arr[mid - 1])
return getNearest(arr[mid - 1], arr[mid], target);
right = mid;
} else {
if (mid < n - 1 && target < arr[mid + 1])
return getNearest(arr[mid], arr[mid + 1], target);
left = mid + 1;
}
}
return arr[mid];
}
int main() {
int arr[] = { 2, 5, 6, 7, 8, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int target = 4;
cout << "Nearest element of " << target << " is: " << getNearestElement(arr, n, target);
} আউটপুট
Nearest element of 4 is: 5
