สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n และมีการจัดเรียงองค์ประกอบ เราต้องหาค่าที่ใกล้เคียงที่สุดกับจำนวนเต็มที่กำหนด อาร์เรย์อาจประกอบด้วยค่าที่ซ้ำกันและตัวเลขติดลบ ดังนั้นหากอาร์เรย์เป็นแบบ [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
