Tìm số gần nhất trong mảng trong C ++

Giả sử chúng ta có một mảng A với n phần tử. Và các phần tử được sắp xếp. Chúng ta phải tìm giá trị gần nhất với số nguyên đã cho. Mảng có thể chứa các giá trị trùng lặp và số âm. Vì vậy, nếu mảng giống như [2, 5, 6, 7, 8, 8, 9] và số mục tiêu là 4, thì phần tử gần nhất là 5.

Chúng ta có thể giải quyết vấn đề này bằng cách duyệt qua mảng đã cho và theo dõi sự khác biệt tuyệt đối của phần tử hiện tại với mọi phần tử. Cuối cùng trả về phần tử có chênh lệch tuyệt đối nhỏ nhất.

Ví dụ

#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);
}

Đầu ra

Nearest element of 4 is: 5