อาร์เรย์เรียงลำดับ (อาจมีค่าซ้ำและค่าลบ) หาค่าที่ใกล้ Target มากที่สุด
ตัวอย่าง: [2, 5, 6, 7, 8, 8, 9], Target = 4 → Closest = 5
อัลกอริทึม Binary Search
- ถ้า Target ≤ arr[0] → คืน arr[0]
- ถ้า Target ≥ arr[n-1] → คืน arr[n-1]
- Binary Search หาจุดที่ Target อยู่ระหว่าง arr[mid-1] และ arr[mid]
- เปรียบเทียบระยะทางกับเพื่อนบ้าน 2 ด้าน คืนค่าที่ใกล้กว่า
ตัวอย่างโค้ด
#include <iostream>
#include <cmath>
using namespace std;
int getNearest(int x, int y, int target) {
return (target - x >= y - target) ? y : 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);
return 0;
}
ผลลัพธ์
Nearest element of 4 is: 5
ความซับซ้อน
เวลา: O(log n), พื้นที่: O(1)
กรณี Equidistant (ห่างเท่ากัน)
โค้ดคืนค่าด้านขวา (y) เมื่อห่างเท่ากัน สามารถปรับได้ตามต้องการ
