একটি সর্টেড (sorted) অ্যারে A দেওয়া থাকলে, X এবং k মান দেওয়া থাকলে, X-এর নিকটতম k সংখ্যক উপাদান বের করতে হবে। X যদি অ্যারেতে থাকে, তবে আউটপুটে দেখানো হবে না। A = [12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56], X = 35, k = 4 হলে আউটপুট: 30, 39, 42, 45।
সমাধান: বাইনারি সার্চ (binary search) ব্যবহার করে ক্রসওভার পয়েন্ট (crossover point) বের করা। ক্রসওভার পয়েন্ট পাওয়া গেলে O(k) সময়ে k-নিকটতম উপাদান প্রিন্ট করা যায়।
উদাহরণ
#include<iostream> using namespace std; int getCrossoverPoint(int arr[], int left, int right, int x) { if (arr[right] <= x) return right; if (arr[left] > x) return left; int mid = (left + right)/2; if(arr[mid] <= x && arr[mid+1] > x) return mid; if(arr[mid] < x) return getCrossoverPoint(arr, mid+1, right, x); return getCrossoverPoint(arr, left, mid - 1, x); } void findKClosestNumbers(int arr[], int x, int k, int n) { int l = getCrossoverPoint(arr, 0, n-1, x); int r = l+1; int count = 0; if (arr[l] == x) l--; while (l >= 0 && r < n && count < k) { if (x - arr[l] < arr[r] - x) cout << arr[l--] << " "; else cout << arr[r++] << " "; count++; } while (count < k && l >= 0){ cout << arr[l--] << " "; count++; } while (count < k && r < n){ cout << arr[r++] << " "; count++; } } int main() { int arr[] ={12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56}; int n = sizeof(arr)/sizeof(arr[0]); int x = 35, k = 5; findKClosestNumbers(arr, x, k, n); } আউটপুট
39 30 42 45 48
